(November-2020-POFM)

A grid of dimensions 2020 is divided into 400 unit squares of dimensions 11. Clara colors each square either white or black, and then Isabelle cuts the grid into rectangles whose sides are contained within the grid. Each of these rectangles must contain at most 2 black squares, and she gives Clara a chocolate each time she cuts a rectangle that contains 0 or 1 black square.

Isabelle chooses her cutting in such a way as to give the fewest chocolates possible to Clara, and Clara chooses her initial coloring in such a way as to get the most chocolates possible from Isabelle. How many chocolates will Isabelle give to Clara?
We will demonstrate for all integers $n>3$ that, if Clara and Isabelle play on a grid of dimensions $n \times n$, Isabelle will give $n$ chocolates to Clara.

Analysis: 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 in the row from left to right, then she cuts just to the right of each of the black squares numbered $2, 4, 6, \ldots$ 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.

Construction: 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 $l$ are two non-negative integers whose sum is $k+l=n-1$.

## PHOTO

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

## 5 Invariants (Xavier)

## Invariants and Colorings

In a combinatorial problem, it often happens that certain quantities are preserved over time, we then speak of invariants. Identifying these quantities can then allow us to prove that a given configuration cannot be reached from a certain initial configuration. To take a simple example, the bishop in chess is at the end of its move on a square of the same color as at the beginning; consequently, if it starts on a white square, it will never end up on a black square. It is important to note that invariants allow us to show an impossibility; to prove that a given configuration is accessible, it is generally necessary to construct an explicit path.