Player A and B play a painful game on the real line. Player A has a pot of paint with four units of black ink. A quantity of this ink suffices to blacken a (closed) real interval of length . In every round, player A picks some positive integer and provides units of ink from the pot. Player B then picks an integer and blackens the interval from to (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 is not completely blackened.
Decide whether there exists a strategy for player A to win in a finite number of moves.
Solution
No, B can ensure that the interval must be completely blackened by the time the ink runs out. At the beginning of round , let be the largest real number such that has already been completely blackened (let .) Suppose A chooses , and let be the integer satisfying
Notice that is the leftmost interval, among those that can be blackened in this round and have not yet been blackened.
B's strategy is to consider the next interval . If has not yet been blackened, then B chooses to blacken ; otherwise, B chooses to blacken . (For convenience, we assume that has already been completely blackened from the start.) To prove that the above strategy works, our goal is to estimate the amount of ink used at the end of each round. We will prove by induction that, if before the start of round , has not yet been completely blackened, then
1. The amount of ink used to blacken is at most .
2. For each , B blackens at most one interval to the right of of the form .
The above conditions clearly hold for . Suppose they hold for all ; then at , consider the interval B blackens.
- If B blackens , it is easy to see that , and hence 1. holds by the induction hypothesis. Moreover, if at the beginning of round there is an interval of length to the right of that has been blackened, then by this strategy it is easy to see that this interval must be , but this contradicts the fact that B chose , a contradiction. Hence 2. also holds.
- If B blackens , but has not yet been completely blackened. It is easy to see that 2. automatically holds. Notice that in this case both and will be blackened, so will advance at least to the right endpoint of , that is, , where . Also notice that any interval that was already blackened before round and intersects must lie within ; by 2., these intervals all have different lengths, and all lengths are greater than , so the amount of ink used on them is less than . Therefore, the amount of ink used on is no more than
Hence 1. also holds. This completes the proof of the induction step.
Now, suppose that after round , has not yet been completely blackened. By 2., the intervals blackened by B in must all have different lengths, with lengths . Hence the amount of ink blackened in is at most . And by 1., the amount of ink blackened in is at most , so the total amount does not exceed , that is to say, the ink has not yet been used up. Therefore A cannot win.