Exercise 13. 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 to Exercise 13 We show that the answer is 15.

First, we can exhibit a coloring with 15 squares colored:

![](https://cdn.mathpix.com/cropped/2024_06_04_0d4f01d8013de0f79932g-20.jpg?height=714&width=717&top_left_y=728&top_left_x=675)

In this coloring, all the squares on the diagonal see exactly one other colored square, and the squares below the diagonal see none, so this coloring is valid.

Now, suppose we have a valid coloring with 16 squares (if we have more, we take any 16 colored squares).

Since it is clearly impossible to have three colored squares in the same row or column, by the pigeonhole principle, there are at least 6 rows and 6 columns with two colored squares. Consider one of these rows, say row $i$. If we consider the leftmost square among the two colored squares in row $i$, we note that this square cannot have another colored square in the same column, say $j$. Indeed, if this potential second square is above $(i, j)$, then the second square would see both colored squares in row $i$, and if the second square were below $(i, j)$, then $(i, j)$ would see both this square and the second square in row $i$. In all cases, we would have a contradiction: there is only one colored square in column $j$.

This reasoning is valid for each of the 6 rows with two colored squares, so we have 6 columns with only one colored square. But we had said that we have 6 columns with two colored squares, which is a contradiction.

Therefore, the maximum number is indeed 15.

$\underline{\text{Alternative Solution } n^{\circ} 1}$ We prove similarly that it is possible to color 15 squares via the previous configuration.

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

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

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

Therefore, the maximum number is indeed 15.

Graders' Comment: The bound of 15 and the construction were found by a significant number of students, but few among them managed to prove its optimality. There were also many submissions claiming to solve the problem but containing flawed proofs. It should be noted that in this type of problem, which involves both a construction part and a proof of optimality, the two parts are independent: the construction rarely serves the proof. Many students invoked an argument along the lines of: "we cannot add more squares to my construction, so it is optimal," which is of course false. For example, we cannot add a colored square to the configuration obtained by coloring only the top-left corner and the bottom-right corner. Many students devised a construction process claiming that each time they made the best choice, without any proof, and at the end claimed that no more than 15 squares (or sometimes 13, or 19, which directly shows that the argument does not work) could be colored. Another common mistake was to claim that the optimal configuration was necessarily obtained by adding colored squares to a configuration maximizing the number of squares such that no one of them has a row and column number greater than those of another: there is no reason for this to be true.