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

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

![](https://cdn.mathpix.com/cropped/2024_05_10_a954a7760d797f08770eg-028.jpg?height=711&width=717&top_left_y=975&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, 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 colored square in row $i$. In either case, 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 had 6 columns with two colored squares, which is a contradiction.

Therefore, the maximum number is indeed 15.

Alternative solution: We prove similarly that it is possible to color 15 squares using the previous configuration.

It is clearly impossible to have 3 squares in the same row. Suppose there are two rows, $a$ and $b$, each containing two colored squares, and 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' comments: The problem was widely attempted, but ultimately few students truly understood the problem statement: some thought that Martin could not even color 10 squares (even though coloring the diagonal was quite natural), and some colored squares in a way that did not match the problem statement at all. Once the configuration in the solution was found, many students simply stated that it was not possible to color more squares and therefore that this was the maximum. However, by coloring $(1,1)$ and $(2,2)$, one can find a configuration where it is not possible to color more squares: yet 2 is not the correct answer. We are also surprised by the few students who noted that there were at most 2 squares per row. This was a simple but important observation, and very few students had the reflex to make it.

## High School Exercises