Exercise 2. Anna and Baptiste are playing the following game. At the beginning of the game, 2022 white squares, numbered from 1 to 2022, are placed in front of them. Then, taking turns, starting with Anna, they choose a white square and color it in the color of their choice: either red or blue. The game ends after 2022 turns, that is, when the last white square is colored.

Anna's score is then equal to the number of integers $a \leqslant 2019$ such that the two squares numbered $a$ and $a+3$ are the same color. Anna wants to have the highest score possible; Baptiste wants Anna's score to be as low as possible. What is the highest score Anna can ensure, regardless of the moves Baptiste chooses to play?
Solution to Exercise 2 For simplicity, we will say that two integers $a$ and $b$ are friends if $a=b \pm 3$. We will say that $a$ is pretty if $a=b-3$ and if $a$ and $b$ are colored the same color, and that $a$ is ugly if $a=b-3$ and if $a$ and $b$ are colored different colors: Anna therefore wants to maximize the number of pretty integers at the end of the game. If $a$ or $b$ is not yet colored, $a$ is neither pretty nor ugly.

Furthermore, for each integer $k=0,1$ and 2, we will denote by $\mathcal{E}_{k}$ the set of integers $n$ such that $1 \leqslant n \leqslant 2022$ and $n \equiv k(\bmod 3)$. We say that a set $\mathcal{E}_{k}$ is started as soon as at least one cell whose number is in $\mathcal{E}_{k}$ has been colored.

We will first demonstrate that Anna can ensure a score of at least 1008 points. To do this, the strategy Anna adopts is as follows.

1. If there exists an integer $a$ that is not yet colored, and a friend, say $b$, is colored, then Anna chooses such an integer $a$ and colors it the same color as $b$; if several integers $a$ and/or $b$ were available, any of these integers $a$ and $b$ will do.
2. If, on the contrary, no such integer $a$ exists, Anna colors a random white cell.

In case 1, the integer $\min \{a, b\}$ becomes pretty, which increases Anna's score by at least 1. In case 2, if a set $\mathcal{E}_{k}$ was already started when Anna is about to play, it means that all its elements were already colored; consequently, with her move, Anna starts a new set $\mathcal{E}_{k}$.

In particular, case 2 occurs at most 3 times during the game, and since Anna plays 1011 moves, case 1 occurs at least 1008 times during the game. As expected, Anna thus ensures a final score of at least 1008 points.

Conversely, we will now demonstrate that Baptiste can prevent Anna from scoring more than 1008 points, regardless of the moves she decides to play. To do this, the strategy Baptiste adopts is as follows.

1. If there exists an integer $a$ that is not yet colored, and a friend, say $b$, is colored, then Baptiste chooses such an integer $a$ and colors it the opposite color to that of $b$; if several integers $a$ and/or $b$ were available, any of these integers $a$ and $b$ will do.
2. If, on the contrary, no such integer $a$ exists, Baptiste colors a random white cell. In case 1, the integer $\min \{a, b\}$ becomes ugly. In case 2, any set $\mathcal{E}_{k}$ already started when Baptiste is about to play was already colored; if $n$ sets were started at that moment, it means that $2022 n / 3=674 n$ moves had already been played, and thus it was actually Anna's turn to play.

Consequently, case 2 never occurs, and since Baptiste plays 1011 moves, there are at least 1011 ugly integers at the end of the game. Furthermore, the three integers 2020, 2021, and 2022 will be neither pretty nor ugly. Among our 2022 integers, there are therefore at least $1011+3$ that will never be pretty, and Anna's score will thus never exceed $2022-(1011+3)=1008$.

Graders' Comments This problem was solved unevenly, with students falling into two main categories: on the one hand, those, quite numerous, who managed to solve the problem; on the other hand, those, equally numerous, who, although they had a reasonable intuition of what could happen, failed to correctly define strategies for Anna and Baptiste.

Students in this second category simply described how, move by move, Anna and Baptiste were supposed to play if they wanted to play optimally. However, this could in no way constitute a proof: in general, when giving a strategy for a player, it is necessary to indicate what moves this player should make even if their opponent plays in an apparently random manner. Incidentally, doing so generally leads to much simpler proofs.

Moreover, the description these students gave was almost systematically incorrect, as Baptiste is not required to directly counter Anna to prevent her from scoring more than 1008 points. For example, if Anna colors the integer 1 red, a relevant strategy for Baptiste could be to color the integer 7 blue.

It is therefore unfortunate that many students end up with very few points, even though they thought they had solved the problem. For these students, it will be very important to remember the proper way to define a strategy for a player, as described above.