Olympiad Maths Prep

Track / Stage 8 / 164 of 180 #1864 of 2000

Problem 1864

IMO Shortlist mid-range; USAMO P2/P5
Combinatorics Difficulty 8.9 Prove it SELECTION TESTS OF THE BELARUSIAN TEAM TO THE IMO · 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)

This one wants a proof. Work it on paper, read the official solution, then mark yourself honestly — the ladder only means something if the record is true.

Official 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.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic, difficulty and ordering added by this site.