Maths Olympiad Prep

Library / /7 of 8

Combinatorics Difficulty 8.9 Shortlist Prove it Belarus

Olya and Tolya have paints of two opposite colors – white and black. They play the following game on the segment [0,1][0, 1]. Each round of the game takes place in two stages: one of the players chooses a number l[0,1]l \in [0, 1], and then the other player chooses some segment J[0,1]J \subseteq [0, 1] of length ll and recolors all its points in the opposite color. In the next round they switch roles and so on.
After 2024 rounds, the total length LL of the white intervals is calculated. If L>12L > \frac{1}{2} then Olya wins, and if L12L \le \frac{1}{2} then Tolya wins. Initially, the entire segment is painted white. Tolya chooses a number first. Who has a winning strategy?
(Andrey Naradzetski)

Solution

Here is a winning strategy for Olya. Denote by LnL_n the total length of the white segments after the nn-th round (L0L_0 is considered to be equal to 1).
Statement. Olya can play in such a way that for k=0,1,,1012k = 0, 1, \dots, 1012 after the (2k)(2k)-th round the total length of the white segments is greater than 12\frac{1}{2} (L2k>12L_{2k} > \frac{1}{2}), and for some δ>0\delta > 0 at least one of the open intervals ]0,δ[]0, \delta[ or ]1δ,1[]1 - \delta, 1[ is completely white.
Let us prove this statement by induction.
The basis for k=0k=0 is obvious.
Assume that after the (2k)(2k)-th round the situation is as described in the statement. Consider Tolya's move in the (2k+1)(2k+1)-th round. If he chooses l=0l=0 or l=1l=1, then Olya can choose the same ll on her turn in the round 2k+22k+2, and the segment [0,1][0, 1] will not change its color, with the exception, perhaps, of two points in the case l=0l=0.

Now suppose that Tolya chose 0<l<10 < l < 1. Since at least one of the outermost open intervals is white, Olya can choose JJ in such a way that after the (2k+1)(2k+1)-th round both outermost open intervals ([0,δ]([0, \delta] or ]1δ,1[]1-\delta, 1[ for some δ>0\delta > 0) were painted white. If L2k+1>12L_{2k+1} > \frac{1}{2}, then Olya simply chooses l=0l = 0. Let's consider the case when L2k+112L_{2k+1} \le \frac{1}{2}. Since the outermost open intervals of the interval [0,1][0, 1] are white, there exists ϵ>0\epsilon > 0 such that the intervals ]0,ϵ[]0, \epsilon[ and ]1ϵ,1[]1-\epsilon, 1[ are white. Then if Olya chooses the number l]1ϵ,1[l \in ]1-\epsilon, 1[, for example l=1ϵ2l = 1-\frac{\epsilon}{2}, then whatever segment JJ Tolya chooses, he will completely cover all black intervals and leave one or two white intervals with a total length of ϵ\epsilon. That is, L2k+2=(1L2k+1)+ϵ>12L_{2k+2} = (1-L_{2k+1}) + \epsilon > \frac{1}{2}. It is also clear that Tolya will not be able to repaint both outermost intervals black at once.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.