Dedalo vs. The Minotaur
Source: Italy MO 2023 P6
May 7, 2023
combinatorics
Problem Statement
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 drachmas, where 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 and for a total of half a drachma, the Minotaur is able to escape using the infinite string .
On the other hand, Dedalo can trap the Minotaur by spending cents of a drachma: he could for example buy the strings and , or the strings .
Determine all positive integers such that Dedalo can trap the Minotaur with an expense of at most cents of a drachma.