Exercise 4. A gardener and a woodpecker play the following game in their garden, which is shaped like a $2022 \times 2022$ grid consisting of $2022^{2}$ cells. Two cells are considered neighbors if they share a vertex or an edge. Initially, each cell contains a tree of size 0. Then, on each turn of the game,

$\triangleright$ the gardener chooses a cell; the trees in this cell and its adjacent cells (a total of four to nine cells) all increase in size by 1;

$>$ the woodpecker then chooses four cells; the trees in these cells all decrease in size by 1 (or remain at 0 if the woodpecker has chosen a cell with a tree of size 0).

A tree is said to be resplendent if its size is at least $10^{6}$. Find the largest integer $A$ such that the gardener can ensure, in a finite number of turns, regardless of the woodpecker's choices, that at least $A$ trees are resplendent.
Solution to Exercise 4: We will demonstrate that the integer sought is $A=5 n=2271380$, where we have set $n=674^{2}=(2022 / 3)^{2}$.

First, here is a strategy for the woodpecker. He numbers the rows and columns from 1 to 2022, then colors black each cell located in a column $c$ and a row $\ell$ for which 3 does not divide either $c$ or $\ell$. Among the four to nine cells on which the gardener acts each turn, at most four are black. The woodpecker then selects the black cells in question; if this results in fewer than four cells, he chooses other cells at random.

By doing so, he ensures that, at the end of the game turn, no tree located in a black cell will have grown taller. An immediate induction indicates that no tree located in a black cell will ever exceed a height of 1, and since there are $4 n$ black cells, it will never be possible to exceed a total of $2022^{2}-4 n=5 n$ splendid trees.

Conversely, here is a strategy for the gardener; we set $m=10^{6}$. Ignoring the coloring imposed by the woodpecker, he colors red each cell located in a column $c$ and a row $\ell$ for which $c \equiv \ell \equiv 2(\bmod 3)$. There are $n$ red cells, and each cell is either red or adjacent to a red cell. The gardener then sets $k=(4 n+1) m+1$ and, during the first $k n$ turns of the game, he chooses each red cell exactly $k$ times. He has thus increased the height of each tree in the garden by $k$.

Let $a$ be the number of trees that are not splendid at the end of this first part of the game: the woodpecker must have chosen each of these $a$ trees at least $k-m$ times. Since he chose $4 k n$ trees during the $k n$ turns of the game, we deduce that $a(k-m) \leqslant 4 k n$, and thus that

$$
(k-m)(a-4 n-1) \leqslant 4 k n-(k-m)(4 n+1)=(4 n+1) m-k
$$

Many students made false dichotomies for the woodpecker's strategy: either he always attacks the same trees, or he flutters uniformly. Of course, intermediates are possible, where the woodpecker mainly targets certain trees but sometimes goes to others.

$\triangleright$ The main error, however, is this: a good strategy for one of the two players having been found, it is absolutely forbidden to use it to find a "reactive" strategy for the other player. Even if you are convinced that the gardener has an interest in playing in the middle of $3 \times 3$ squares, it is impossible to assume this to describe the woodpecker's strategy. Even if you are convinced that the woodpecker has an interest in choosing a certain number of trees against which he harbors a thousand-year-old grudge and to attack them as soon as the gardener tries to make them grow, it is impossible to assume this to describe the gardener's strategy. Indeed, even if there are optimal strategies for each of the two players that meet these reasonable constraints, there are also equally effective strategies that do not work this way.

Here is how to proceed for a confrontation between two players: the proof must be divided into two completely separate parts that will not share any common argument. On the one hand, a strategy for the woodpecker must be given that ensures a certain score even if the gardener plays chaotically. It is then crucial to make no assumptions about the gardener's strategy and to avoid false dichotomies; the gardener should be allowed to "play badly" in this part if he wishes, as it is always simpler than justifying that his "bad" move could not become good in a distant future. In the second half of the proof, everything is reversed, a strategy for the gardener is given that remains valid even if the woodpecker does not follow the strategy just described, even if he also plays chaotically, without making any assumptions about his strategy.