There are $100$ white points on a circle. Asya and Borya play the following game: they alternate, starting with Asya, coloring a white point in green or blue. Asya wants to obtain as much as possible pairs of adjacent points of distinct colors, while Borya wants these pairs to be as less as possible. What is the maximal number of such pairs Asya can guarantee to obtain, no matter how Borya plays.
Problem
Source: ARO Regional stage 2024 10.3=11.3
Tags: combinatorics
02.02.2024 17:19
The answer is 50. Very important fact in one of strategy for first player is that in the end number of such pairs is always even. For example, players can add or ban one such pairs every theirs move. This works.
18.02.2024 18:28
Answer: $50$. Strategy for $B$: Label the points as $1,2,...,100$. $B$ pairs $2i-1$ with $2i$. $B$ colours the pair of the point which $A$ coloured before $B'$s move with the same colour so there can be at most $50$ different coloured neighbours. Strategy for $A$: Label the points as $1,2,...,100$. $A$ pairs $2i$ with $2i+1$ for $i=1,2,...,49$ such that each number except $1$ and $100$ has one pair. $A$ colours $1$ as red. After that, if $B$ colours a number, then $A$ colours its pair with the other colour. So there are at least $49$ different coloured pairs. Assume that there are $49$ of them. Then, there mustn't be any different coloured neighbours between two points in distinct pairs. But this is not possible since $49$ is odd. More explicitly, the colours must be $1\rightarrow R, 2\rightarrow R, 3\rightarrow G, 4\rightarrow G, 5\rightarrow R,...,97\rightarrow R,98\rightarrow R, 99\rightarrow G$ hence $100$ is in the same colour with exactly one of $1,99$. This gives that there cannot be $49$ distinct coloured pairs. So $A$ can achieve that there are at least $50$ distinct coloured neighbours.$\blacksquare$