The only possible values for $c$ are $0, 25, 50, 75, 100, 125, 150, 175 \dots $ because $\frac{c}{100}$ must be a fraction of a power of 2. I also see that we can inflate the price at any time by buying random strings that don't actually affect the game. For example we can achieve 125 by buying $0, 00, 01, 11$ and 150 by buying $0, 1, 00, 11$. We can also increase the price by 1 by buying all possible strings of length $n$ where we haven't used any strings of length $n$ so far which is always possible because Dedalo is buying a finite number of strings and there are countably infinite n to choose from. From this we already know that $c$ can be $75, 100, 125, 150, 175 \dots$. This leaves us to only show solutions for 25 and 50 which I believe are both impossible (tho idk the proof for it)

Almora wrote: The only possible values for $c$ are $0, 25, 50, 75, 100, 125, 150, 175 \dots $ because $\frac{c}{100}$ must be a fraction of a power of 2. I also see that we can inflate the price at any time by buying random strings that don't actually affect the game. For example we can achieve 125 by buying $0, 00, 01, 11$ and 150 by buying $0, 1, 00, 11$. We can also increase the price by 1 by buying all possible strings of length $n$ where we haven't used any strings of length $n$ so far which is always possible because Dedalo is buying a finite number of strings and there are countably infinite n to choose from. From this we already know that $c$ can be $75, 100, 125, 150, 175 \dots$. This leaves us to only show solutions for 25 and 50 which I believe are both impossible (tho idk the proof for it) It says at most $c$ not exactly $c$

a_507_bc wrote: 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. Construction for $c=44$. First fix some $n$ that will be the number of digits of numbers we will choose (note that we can artificialy increase $n$ by one without affecting $c$ by making two copies of old string one with 1 and other one with 0 added at the end). We now take all binary strings of length $2^n$ that start with two ones or end with two zeroes, there are $2^{n-4}*7$ numbers of this form. This ensures that there do not exist two consecutive zeroes ir two consecutive ones. Now we simply add 101010101.... and we are done. This gives us $c>\frac{700}{16}$ and $\frac{700}{16}<44$ so we get $c=44$ for some big enough $n$.

The answer should be any $c$

Just like for solution without $2$ consecutives take some huge $n$ and some big $k$ and choose numbers so that there is no $k+1$ same consecutive numbers in Minotaurs string. Then we will choose all of the binary strings of length $n$ without $k+1$ consecutive numbers their total number is actually $n$-th k-bonacci number. Ratio of two consecutive k-bonacci numbers converges to largest solution of $x^k = x^{k-1}+x^{k-2}...+1$ so for big enough $k$ it will be just a little under two. So for big enough $n$ we can get $2^{n-k+1}/2^n$ which converges to zero for big enough $n$. So he can buy all of the strings he needs for $c=1$.

Complete_quadrilateral wrote: Do you know how many contestants did this problem? Two

Take a big $n$ and use the strings with $n+1$ $1$s and the string with $n+1$ $0$s. These cost $\frac{1}{2^n}$ total. Now any possible valid string can only have at most $n$ consecutive bits that are equal. Replace the binary string with an integer array depicting the length of consecutive equal blocks. For example 011000100... becomes 12312... Choose a big $m$. We pick the binary string corresponding to every possible $m$ length array. For example if $n=2$ and $m=3$ we would take $010$, $0100$, $0110$, $01100$, $0010$, $00100$, $00110$, $001100$ and their complementaries. We calculate the cost. It is equal to $2(\frac{1}{2}+\frac{1}{4}+\cdots+\frac{1}{2^n})^m$ by generating functions (the first factor of 2 is because it can start with $0$ or $1$). This is equal to $2(1-\frac{1}{2^n})^m$. Hence we have found a construction with cost $\frac{1}{2^n}+2(1-\frac{1}{2^n})^m$, and taking $m,n$ sufficiently large finishes.

What's the format of ITAMO? Is it 2 days with 3 problems each like imo or what? Cus 3rd problem is so much easier than this one

It's one day exam with 6 problems