Browse · MathNet
PrintSELECTION TESTS OF THE BELARUSIAN TEAM TO THE IMO
Belarus counting and probability
Problem
Olya and Tolya have paints of two opposite colors – white and black. They play the following game on the segment . Each round of the game takes place in two stages: one of the players chooses a number , and then the other player chooses some segment of length 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 of the white intervals is calculated. If then Olya wins, and if 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 the total length of the white segments after the -th round ( is considered to be equal to 1). Statement. Olya can play in such a way that for after the -th round the total length of the white segments is greater than (), and for some at least one of the open intervals or is completely white. Let us prove this statement by induction. The basis for is obvious. Assume that after the -th round the situation is as described in the statement. Consider Tolya's move in the -th round. If he chooses or , then Olya can choose the same on her turn in the round , and the segment will not change its color, with the exception, perhaps, of two points in the case .
Now suppose that Tolya chose . Since at least one of the outermost open intervals is white, Olya can choose in such a way that after the -th round both outermost open intervals or for some ) were painted white. If , then Olya simply chooses . Let's consider the case when . Since the outermost open intervals of the interval are white, there exists such that the intervals and are white. Then if Olya chooses the number , for example , then whatever segment Tolya chooses, he will completely cover all black intervals and leave one or two white intervals with a total length of . That is, . It is also clear that Tolya will not be able to repaint both outermost intervals black at once.
Now suppose that Tolya chose . Since at least one of the outermost open intervals is white, Olya can choose in such a way that after the -th round both outermost open intervals or for some ) were painted white. If , then Olya simply chooses . Let's consider the case when . Since the outermost open intervals of the interval are white, there exists such that the intervals and are white. Then if Olya chooses the number , for example , then whatever segment Tolya chooses, he will completely cover all black intervals and leave one or two white intervals with a total length of . That is, . It is also clear that Tolya will not be able to repaint both outermost intervals black at once.
Final answer
Olya
Techniques
Games / greedy algorithmsInvariants / monovariants