MathDB

Dedalo buys a finite number of binary strings, each of finite length and made up of the binary digits 0 and 1. For each string, he pays

(\frac{1}{2})^L

drachmas, where

L

is the length of the string. The Minotaur is able to escape the labyrinth if he can find an infinite sequence of binary digits that does not contain any of the strings Dedalo bought. Dedalo’s aim is to trap the Minotaur. For instance, if Dedalo buys the strings

00

and

11

for a total of half a drachma, the Minotaur is able to escape using the infinite string

01010101 \ldots

. On the other hand, Dedalo can trap the Minotaur by spending

75

cents of a drachma: he could for example buy the strings

0

and

11

, or the strings

00, 11, 01

. Determine all positive integers

c

such that Dedalo can trap the Minotaur with an expense of at most

c

cents of a drachma.

6

Problems(1)