I don't know what is wrong with this greedy argument, but it seems to work for any integer amount of paint. Player $B$ will choose the smallest possible $k$ such that the interval $[k/2^m,(k+1)/2^m]$ is totally white. If that interval is outside $[0,1]$, who cares, $B$ still plays outside that interval. Then $B$ will announce this strategy to $A$, so it becomes a 1 player game. So now suppose $A$ has a winning strategy. Consider the winning strategy to play $m=m_1,...,m_n$, where $n$ is the smallest possible. Let $B$ play $k_1,...,k_n$. Suppose $m_p>0$ is the maximum, then it has to appear at least twice - $m_p$ and $m_q$ the second time with $q>p$. Then suppose $B$ plays $k_i$ when $A$ plays $m_i$. Then note that $k_p$ has to be even. Then $k_q>k_p$ since $B$ always play greedily $k_p$ is already minimum. Also $[(k_p+1)/2^{m_p},(k_p+2)/2^{m_p}]$ has to be white. So $k_q=k_p+1$. Note that this is equivalent to replacing $m_p$ with $m_p-1$ and remove $m_q$. So $A$ has a smaller winning strategy, contradiction. Thus any winning strategy must have $m_i=0$, which is clearly not a winning strategy. So $A$ doesn't have a winning strategy.

Huh? $A$ plays $1, 2, 1, 1, 1, \ldots$. $B$ will cover $[0, 0.5]$, then $[0.5, 0.75]$, then he will never return to the interval $[0,1]$.

But $A$ must play a total of an integer amount of paint, so at some point he will have to play $2$ again.

Ah, missed that. I was just maximizing the amount of ink; I forgot that A must play exactly that much ink. Yes, that seems to work. Is the solution really greedy? If so, this is C8 just because one wouldn't expect greedy to be the solution.

We discussed this solution during Canadian training this year. I think it's correct but represents an easily fixable oversight by the jury/selection committee/proposer. I suggest the following re-formulation which I think cannot be solved with greedy: --- Players $A$ and $B$ play a "paintful" game on the real line. Player $A$ has an infinite pot of paint. A quantity $p$ of this ink suffices to blacken a (closed) real interval of length $p$. In every round, player $A$ picks some positive integer $m$ and provides $1/2^m $ units of ink from the pot. Player $B$ then picks an integer $k$ and blackens the interval from $k/2^m$ to $(k+1)/2^m$ (some parts of this interval may have been blackened before). The goal of player $A$ is to reach a situation where at least 4 ink from the pot is used and the interval $[0,1]$ is not completely blackened. Decide whether there exists a strategy for player $A$ to win in a finite number of moves --- The difference here is that $A$ is allowed to use more than 4 ink, which means it's no longer true that $A$ must pick the smallest interval twice. I believe the official solution still works in this scenario. Actually it works even if 4 is replaced by 3 - not sure why 4 was chosen. By the way, I asked the leader of the team from last year whether the jury was aware of the greedy solution, and he says they were not.

Do you have the official solution? I'd certainly like to see that.

chaotic_iak wrote: Do you have the official solution? I'd certainly like to see that. They actually post solutions on the official website nowadays: http://www.imo-official.org/problems/IMO2013SL.pdf

I don't understand why there should exist p and q such that m(p) and and m(q) are equal in oneplusone's solution?Also why k(q)=k(p)+1? Any help is appreciated.

guesswho1729 wrote: I don't understand why there should exist p and q such that m(p) and and m(q) are equal in oneplusone's solution?Also why k(q)=k(p)+1? Any help is appreciated. Choose $m_p$ to be a maximum. Since this is the maximum and A must play an integer amount of paint (4 in this case), A must play $m_p$ again. You can think of it like this: $\sum\frac{1}{2^{m_i}}=4$, so $\sum2^{m_p-m_i}=4 \cdot 2^{m_p}$. If there was only one $m_p$ played, then the LHS would be odd and the RHS would be even. Contradiction. $k_q=k_p+1$ because B will not play $m_i$ in an interval $[k/2^{m_i},(k+1)/2^{m_i}]$ containing $[(k_p)/2^{m_p},(k_p+1)/2^{m_p}]$. On the other hand, $m_i < m_p$, so any interval $[k/2^{m_i},(k+1)/2^{m_i}]$ containing $[(k_p)/2^{m_p},(k_p+1)/2^{m_p}]$ must also contain $[(k_p+1)/2^{m_p},(k_p+2)/2^{m_p}]$, so $[(k_p+1)/2^{m_p},(k_p+2)/2^{m_p}]$ is white and since $k_q>k_p$, $k_q=k_p+1$. Another question about oneplusone's solution: What is the minimum required amount of paint given to A for his solution to work. A general question: The official solution gave a variant of this problem: Players $A$ and $B$ play a "paintful" game on the real line. Player $A$ has a pot of paint with four units of black ink. A quantity $p$ of this ink suffices to blacken a (closed) real interval of length $p$. In the beginning of the game, player A chooses (and announces) a positive integer $N$. In every round, player $A$ picks some positive integer $m \leq N$ and provides $1/2^m $ units of ink from the pot. Player $B$ then picks an integer $k$ and blackens the interval from $k/2^m$ to $(k+1)/2^m$ (some parts of this interval may have been blackened before). The goal of player $A$ is to reach a situation where the pot is empty and the interval $[0,1]$ is not completely blackened. Decide whether there exists a strategy for player $A$ to win in a finite number of moves. The problem selection committee said this variant would be harder. How come? A anyways will lose, so bounding the amount of paint he can use will just make his life harder. Any answers for these will be greatly appreciated!

Anyone???

MathPanda1 wrote: Another question about oneplusone's solution: What is the minimum required amount of paint given to A for his solution to work. A general question: The official solution gave a variant of this problem: Players $A$ and $B$ play a "paintful" game on the real line. Player $A$ has a pot of paint with four units of black ink. A quantity $p$ of this ink suffices to blacken a (closed) real interval of length $p$. In the beginning of the game, player A chooses (and announces) a positive integer $N$. In every round, player $A$ picks some positive integer $m \leq N$ and provides $1/2^m $ units of ink from the pot. Player $B$ then picks an integer $k$ and blackens the interval from $k/2^m$ to $(k+1)/2^m$ (some parts of this interval may have been blackened before). The goal of player $A$ is to reach a situation where the pot is empty and the interval $[0,1]$ is not completely blackened. Decide whether there exists a strategy for player $A$ to win in a finite number of moves. The problem selection committee said this variant would be harder. How come? A anyways will lose, so bounding the amount of paint he can use will just make his life harder. Any answers for these will be greatly appreciated! I think any integer will work for oneplusone's solution (great solution by the way! ). Greedy means that we always pick an interval that is totally white, and so no drop of ink is wasted. So as long as you have an integer $n$ amount of ink, at the end you will have covered $[0, n]$ completely. Note that this doesn't work for fractional values besides those of the form $\frac{k}{2}$, see chaotic_iak's idea for why. I think the PSC and perhaps the jury too were confused by the statement of the problem and assumed it to be equivalent to the formulation david arthur suggested above. Then they were expecting the official estimation solution, and the neat wrap-ups performed with infinite sums wouldn't have worked out with an upper bound on $m$. Of course the issue can be fixed with a small argument in the vein of oneplusone's proof, but maybe PSC considered it to be adding more difficulty/confusion to an already difficult problem. It might seem a bit silly now that we know the greedy solution, but it might be retty daunting in contest conditions.

Interesting, yeah, I agree it might be more daunting in contest conditions. Thank you Zawadx for all your help!

SOLVED WITH MY IDOLS stroller AND Aryan-23!!! Darn classic greedy algorithms. Also congratulations to the proposer on intentionally tricking us with that 4. Here's a write up that in was completely motivated by a smart observation: Solution wrote: We shall proceed by contradiction to show that A can not win. In addition, assume that B plays greedily. So suppose A had a winning strategy, say $m_1,\ldots,m_n$ and B responds with $k_1,\ldots,k_n$. The following claim kills the problem: Claim. Suppose that $m_r=\max(m_1,\ldots,m_n)$. Then there exists $s\neq r$ with $m_r=m_s$. Proof. Assume the contrary. Now, multiplying the total amount of paint A uses by $2^{m_r-1}$, we should get $2^{m_r+1}$ total paint was used. But we have a $\frac 12$ with no match, a contradiction. Oh wait, another claim: Claim. For $r$ defined above (and the minimum such $r$), $k_r$ is even (when B plays greedily). Proof. Assume the contrary, so $k_r=2k+1$ and for simplicity let $m=m_r$. As this is the minimum $p$ such that $\left[\frac p{2^m},\frac{p+1}{2^m}\right]$ is not filled, we note that $\left[\frac {2k}{2^m},\frac{2k+1}{2^m}\right]$ is filled. However, as all our intervals are of length $2^{1-m}$ or more, so in particular, the entire interval $\left[\frac {2k}{2^m},\frac{2k+2}{2^m}\right]$ is filled, a contradiction. To finish, note that we can assume that A's aforementioned series of moves has shortest length. Then we can combine the moves $m_r$ and $m_s$ and B picks $\frac{k_r}2$, completing the proof and showing $A$ is doomed.

I think only 1 unit of black ink is needed? If so, why put 4? This is way too high? Shortlist says 3 can be done... but 1? Honestly so confused. Let me know why this fails. I claim $A$ cannot win. Allow $A$ to submit $m = 0$. For now consider $A$ to have a pot of 1 unit. Assume $A$ can win in a finite number of moves. Then since B only has only a finite number of moves on each turn ($0 \leq k < 2^{m}$), by Konig's lemma, $A$ can always win within some constant number of moves. Thus $A$'s winning strategy has finitely many branches, so $A$ can win by only using values $m$ smaller than some constant. We will show this is impossible. We call a configuration $n$-good if no matter what $A$ chooses from the pot for $m \leq n$, $B$ can move in a way that returns to a good configuration, where the totally filled interval is considered good. Notice that $B$ can ensure he stays good if and only if he never overlaps his intervals. Hence in a good configuration, the sum of lengths of uncovered segments of the interval must equal the paint in the pot. Claim: For all fractions $\frac{a}{2^n}$ where there exists the rule $m \leq n$, there exists a $n$-good configuration where $\frac{a}{2^n}$ of the interval is filled. We call $a$ the size of the $n$-good configuration. Proof: We proceed with induction. For $n = 0$ it is trivial. Inductive step: We prove $n+1$ given $n$. Split the interval of $2^{n+1}$ into two halves, each with $2^n$ segments. Notice these halves are mutually disjoint in terms of the effect of operations, with the only exception being the values of $m$ that $A$ may call since $A$ has access to the combined pots from both games of $2^n$ segments. I claim that if a configuration is composed of two $n$-good segments of size $2^n - a, 2^n - b$ with the binary representations of $a, b$ disjoint, it is $n+1$-good. If the number $A$ chooses to fill in is in the binary representation of either good segment, removing it suffices, since by definition that $n$-good segment is capable of removing a segment of that size by the inductive hypothesis, and the condition on $a, b$ is preserved. If it does not belong to either binary string, simply look at the next largest digit, and so on. Removing it from this $n$-good segment is possible by the inductive hypothesis, and it is obvious that the condition on $a, b$ is preserved since if it is removed from $b$, then all of the digits in $b$ which become $1$ must have been empty in the binary string of $a$ by our construction. Hence both conditions are always preserved, so since $A$ can only call finitely many times, eventually the configuration must reach an completely filled interval, as desired. Also notice now that $(a, b) = (2^n, 2^n)$ is also good (it is not included in the condition) since all of $(a, b) = (k, 2^n)$ for $k < 2^n$ are good. $(a, b) = (0, 0), (0, 1), (0, 2), (0, 3), \ldots, (0, 2^n-1), (0, 2^n), (1, 2^n), (2, 2^n), (3, 2^n), \ldots, (2^n, 2^n)$ are good, and these sum to all values between $0$ and $2^{n+1}$, so we are done. $\blacksquare$ So it follows that whatever the constant $m \leq n$ is, $(2^n, 2^n)$, the initial position, is good, as desired, so $A$ cannot win under this strategy for $B$. Now let's return to the original problem. Whenever $A$ calls $\frac{1}{2^k}$, just interpret it as $\frac{1}{2^{k+2}}$ in our alternate game and fill in the corresponding interval of $[0, 1]$ scaled up to $[0, 4]$. $B$ can prevent $A$ from winning the original game, it follows that we can guarantee all of $[0, 4]$ is filled in, finishing since $[0, 1] \subset [0, 4]$. EDIT: Oh wow greedy just works, great