2. Consider an $n \times n$ table, with $n \geqslant 1$. Aya wants to color $k$ cells of this table so that there is a unique way to place $n$ tokens on colored cells without any two tokens being in the same row or the same column. What is the maximum value of $k$ for which Aya's wish is achievable?

## Solutions
Solution 1 First, Aya can choose the diagonal, which we will call $D$, consisting of the cells with coordinates $(x, x)$. Aya then proceeds to color all the cells located on $D$ or above $D$. Step by step, we observe that she has no other choice but to place her $n$ tokens on the diagonal $D$ itself. Furthermore, by doing so, she colors $1+2+\cdots+n=n(n+1) / 2$ cells. Thus, $k \geqslant n(n+1) / 2$.

Conversely, consider a coloring of $k$ cells that satisfies the conditions of the problem, and the only possible arrangement of the tokens on these $k$ cells. Even if we exchange any two rows of the table, our coloring will still satisfy the conditions of the problem. Therefore, and without loss of generality, we assume that the tokens are on the diagonal $D$ by successively exchanging rows of the table.

We then group the cells outside of $D$ into pairs: each cell with coordinates $(x, y)$ is paired with the cell that is symmetric to it with respect to $D$, i.e., the cell with coordinates $(y, x)$. If our coloring contained two cells of the same pair, say the cells $(x, y)$ and $(y, x)$, Aya could have removed the tokens from the cells $(x, x)$ and $(y, y)$ and placed them in the cells $(x, y)$ and $(y, x)$. Therefore, our coloring contains at most one cell from each pair. Since the diagonal has $n$ cells and the other cells are distributed into $n(n-1) / 2$ pairs, we have thus colored at most $n+n(n-1) / 2=n(n+1) / 2$ cells, so that $k \leqslant n(n+1) / 2$.

We conclude that $k=n(n+1) / 2$.

![](https://cdn.mathpix.com/cropped/2024_06_04_af7eccc56af1694588e1g-2.jpg?height=417&width=417&top_left_y=1605&top_left_x=868)