IT-CESENATICO 2023 Problem 6

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.