Exercise 8. A gardener and a woodpecker play the following game in their garden, which is in the shape of a $2022 \times 2022$ grid consisting of $2022^{2}$ cells. Two cells are considered adjacent 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 in the adjacent cells (a total of four to nine cells) all increase in size by 1;

$\triangleright$ 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 8 We will show that the integer sought is \( A = 5n = 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 chooses the black cells in question; if there are fewer than four, he chooses other cells at random.

By doing this, he ensures that, at the end of the turn, no tree located in a black cell will have grown. An immediate induction indicates that no tree located in a black cell will ever exceed a height of 1, and since there are \( 4n \) black cells, it will never be possible to exceed a total of \( 2022^2 - 4n = 5n \) 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 \pmod{3} \). There are \( n \) red cells, and each cell is either red or adjacent to a red cell. The gardener then sets \( k = (4n + 1)m + 1 \) and, during the first \( kn \) turns of the game, he chooses each red cell exactly \( k \) times. Thus, he has 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 \( 4kn \) trees during the \( kn \) turns of the game, we deduce that \( a(k - m) \leq 4kn \), and therefore that

\[
(k - m)(a - 4n - 1) \leq 4kn - (k - m)(4n + 1) = (4n + 1)m - k < 0
\]

Since \( k \geq m \), this means that \( a < 4n + 1 \), and thus \( a \leq 4n = 9n - A \).

In conclusion, the integer sought is indeed \( A = 5n \).

Comment from the graders The problem was widely addressed but poorly handled overall. Many papers provide reasonable strategies for the players without justifying that they are truly optimal, or provide an optimal strategy assuming the other player follows the previously described reasonable strategy.

There were two parts to this problem, which were rarely well separated:

\(\triangleright\) provide a strategy for the woodpecker, valid even if the gardener acts chaotically, and

\(\triangleright\) provide a strategy for the gardener, valid even if the woodpecker acts chaotically.

A justification of the gardener's strategy cannot start with "if the woodpecker plays as well as possible for him," because the strategy must work completely independently of the other player. For example, providing a tiling was the right way to justify the woodpecker's strategy, since regardless of the gardener's choices, the woodpecker can adapt. Readers are strongly encouraged to read the comments made about Problem 4, which had the same statement but was intended for Junior group students.

Most students, however, managed to develop a good intuition for the correct bound, which was not obvious.