Exercise 7. Consider a $10 \times 10$ grid, composed of 100 cells. The rows of the grid are numbered from top to bottom in the order of 1 to 10: the topmost row has the number 1, the bottommost row has the number 10. The columns of the grid are numbered from left to right in the order of 1 to 10: the leftmost column has the number 1, the rightmost column has the number 10. Martin colors some cells of the grid such that for any colored cell $c$, there is at most one different colored cell whose column number is greater than or equal to that of the column of $c$ and whose row number is greater than or equal to that of the row of $c$.

What is the maximum number of cells that Martin can color?
Solution alternative $n^{\circ} 1$ We similarly prove that it is possible to color 15 cells through the previous configuration.

It is clearly impossible to have 3 cells in the same row. Suppose there exist two rows, $a$ and $b$ each containing two colored cells and such that row $a$ is above row $b$. Then the left cell in row $a$ must be strictly to the right of the right cell in row $b$. Indeed, if this were not the case, the cell would see both the right cell in row $a$ and the left cell in row $b$, which is impossible.

Thus, all cells belonging to rows containing 2 colored cells are in different columns. There are at most 10 cells belonging to rows containing 2 colored cells, so there are at most 5 rows containing two colored cells.

Thus, there are at most $5 + 5 \times 2 = 15$ colored cells.

The maximum number is therefore 15.

Graders' comment: The problem was widely attempted, but ultimately few students truly understood the statement: some thought that Martin could not even color 10 cells (while coloring the diagonal was quite natural), and some colored cells in a way that did not correspond at all to the statement. Once the configuration of the