Exercise 15. Théo places tokens in the cells of a $30 \times 30$ grid while following these rules:

$\triangleright$ Each cell contains at most one token.

$\triangleright$ For each empty cell, there is, among the cells in the same row or the same column, at least one cell containing a token.

$\triangleright$ For each token, there is, among the cells in the same row or the same column, at most one other cell containing a token.

Determine the smallest integer $k$ satisfying the following property: regardless of the arrangement chosen by Théo, each $k \times k$ square of the grid contains at least one cell with a token.
## Solution to Exercise 15

Answer: $k=21$

In this exercise, we aim to demonstrate that 21 is the smallest integer satisfying the property stated in the problem. The solution necessarily includes two parts. First, we show that if, regardless of the arrangement of tokens, each $k \times k$ square contains a token, then $k \geqslant 21$; this step is called the analysis. Second, we show that in the case where $k=21$, regardless of the arrangement, every $k \times k$ square contains at least one token; this step is called the synthesis.

## Analysis:

Consider the following configuration: on the $i$-th row from the top, with $i \leqslant 10$, place a token on the cell at the intersection with column $2i-1$ and a token on the cell at the intersection with column 2. The figure below on the left shows this construction for a $12 \times 12$ square:
![](https://cdn.mathpix.com/cropped/2024_06_04_17def46ea4e6119381e4g-29.jpg?height=628&width=1322&top_left_y=1469&top_left_x=367)

The figure on the right gives another possible construction.

Thus, if $k$ satisfies the property, then $k \geqslant 21$.

## Synthesis:

We need to show that for any configuration of tokens satisfying the properties, every $21 \times 21$ square contains at least one token.

Suppose this is not the case and that there exists a configuration of tokens in which the table contains a $21 \times 21$ square without any tokens. By swapping certain rows and columns if necessary, we assume that this square is the one that contains the bottom-left corner of the table.

We then consider the following scheme:

![](https://cdn.mathpix.com/cropped/2024_06_04_17def46ea4e6119381e4g-30.jpg?height=617&width=619&top_left_y=114&top_left_x=724)

Since there are at most two tokens per row, the first 9 rows from the top together contain at most 18 tokens. Therefore, part $A$ contains at most 18 tokens. Since part $A$ has 21 columns, there is at least one column that does not contain any tokens. Similarly, by reasoning about $B$, we can extract at least one row that does not contain any tokens. However, the cell at the intersection of this row and this column does not satisfy the property stated in the problem, which is absurd.

Comment from the graders: The exercise was rarely attempted due to its position and was a good problem to distinguish the very best students. A significant number of students did not understand the problem statement. Few students correctly identified the value of the integer $k$ in the problem, without which it was difficult to make progress. Among those who found the correct value of $k$, some provided an example of a construction with a $20 \times 20$ square without tokens and declared without any proof that by so-called optimality, $k=21$ does not work. No formal argument can be based on this. Some showed that for $k=21$, there is always a token, and forgot to provide an example for $k=20$. And some did neither, justifying their value with a heuristic that was often unconvincing and without any points.

Be careful, many claimed that every row and column contains a token, which is entirely false and greatly simplifies the proof.