Exercise 1. A grid of dimensions $20 \times 20$ is divided into 400 unit squares of dimensions $1 \times 1$. Clara colors each square either white or black, and then Isabelle cuts the grid into rectangles whose sides lie along the grid lines. Each of these rectangles must contain at most 2 black squares, and she gives Clara a chocolate for each rectangle that contains 0 or 1 black square.

Isabelle chooses her cutting to give the fewest chocolates possible to Clara, and Clara chooses her initial coloring to get the most chocolates possible from Isabelle. How many chocolates will Isabelle give to Clara?
Solution to Exercise 1 We will prove for all integers $n \geqslant 3$ that, if Clara and Isabelle play on a grid of dimensions $n \times n$, Isabelle will give $n$ chocolates to Clara.

First, to limit the number of chocolates she will give to Clara, Isabelle can proceed as follows. She starts by cutting the rectangle into $n$ rows, and prepares to subdivide each row into rectangles. To do this, she numbers the black squares from left to right, then cuts just to the right of each of the black squares numbered 2, 4, 6, etc. By doing so, all the rectangles obtained, except possibly the last one, contain two black squares. Thus, Isabelle gives at most $n$ chocolates to Clara.

![](https://cdn.mathpix.com/cropped/2024_06_04_cd4fc77c7d27ff991455g-2.jpg?height=508&width=512&top_left_y=1005&top_left_x=772)

Conversely, suppose Clara colors her $n \times n$ grid with the following coloring, where we have distinguished with two shades of gray the squares that Clara colors black, and where $k$ and $\ell$ are two non-negative integers whose sum is $k+\ell=n-1$.

![](https://cdn.mathpix.com/cropped/2024_06_04_cd4fc77c7d27ff991455g-2.jpg?height=956&width=945&top_left_y=1715&top_left_x=561)

If a rectangle contains exactly two black squares, they are adjacent: one dark gray and one light gray. There are $(k+1)(\ell+1)$ dark gray squares and $k \ell$ light gray squares. Therefore, Isabelle can draw at most $k \ell$ rectangles covering exactly two black squares, and these rectangles leave aside $k+\ell+1=n$ dark gray squares. This forces Isabelle to give at least $n=20$ chocolates to Clara.

Comment from the graders The main difficulties of this exercise were as follows:

1. convincing oneself that Clara can force Isabelle to give her at least 2 chocolates;
2. finding a coloring that forces Isabelle to give at least 20 chocolates;
3. proving that this coloring indeed forces Isabelle to give at least 20 chocolates;
4. finding a simple strategy that allows Isabelle to give at most $n$ chocolates.

Many students were stuck at the first difficulty, simply noting that Isabelle would give at least one chocolate if the grid was empty or contained an odd number of black squares, but making the incorrect assertion:

If Clara draws a non-zero even number of black squares, Isabelle can pair these squares to give no chocolates to Clara.

Once such a property was incorrectly considered as established, these students did not even attempt to address difficulties 2 to 4.

From a methodological point of view, it is a pity that these students did not take the time to carefully study the cases of small grids, since the $2 \times 3$ and $3 \times 3$ rectangular grids provided a clear counterexample to this assertion, as illustrated below.
![](https://cdn.mathpix.com/cropped/2024_06_04_cd4fc77c7d27ff991455g-3.jpg?height=274&width=686&top_left_y=1381&top_left_x=684)

Moreover, by looking for the simplest possible arguments to explain why such configurations forced Isabelle to give 2 or even 3 chocolates, students could have had the idea of the gray shade coloring; or, at the very least, noticed that two black squares contained in the same rectangle of Isabelle were necessarily adjacent.

Furthermore, several students correctly identified the cross-shaped motif in the $3 \times 3$ grid, but did not think to try to generalize it to the $4 \times 4$ case: the few students who followed such an approach all arrived at a complete solution, proposing the construction presented above in the case where $k=\lfloor n / 2\rfloor$ or $k=1$.

Several students, having searched for but not found a coloring that would force Isabelle to give $n$ chocolates, nonetheless successfully undertook to show that Isabelle would give between $n / 2$ and $n$ chocolates to Clara. More generally, the graders are pleased to note that many students had the idea of separately seeking lower and upper bounds on the number of chocolates Isabelle would give, that is, of seeking a good strategy for Isabelle and a good coloring for Clara, and then proving that such a coloring was good. In fact, students who followed such an approach were very often rewarded with a substantial number of points, even when they did not find an optimal coloring.

Finally, here are three very avoidable errors that the graders found in many papers.
$\triangleright$ Several students, explaining how Isabelle could manage to give no more than 20 chocolates, incorrectly wrote that, in the case of a row with an even number of black squares, Isabelle would give no chocolates. This assertion is incorrect, as Isabelle must still give a chocolate if the row contains no black squares.

$\triangleright$ Other students, while attempting to prove that a coloring by Clara would force Isabelle to give her at least 20 chocolates, assumed that Isabelle would cut the grid into rectangles of width 1. Even if such considerations indeed showed that the technique of cutting the grid into strips would not allow Isabelle to give fewer than 20 chocolates, this assumption was unfounded, as Isabelle would already have to give 20 chocolates even when the grid is empty.

$\triangleright$ Finally, some students, starting from an optimal configuration, attempted to prove that it could not be improved by changing the color of a single square. But nothing prevented changing the color of several squares, and such reasoning was therefore null and void: exhibiting a local maximum (which was done here) is clearly insufficient to prove that it is in fact a global maximum.