We consider an $n \times n$ table, with $n\ge1$. Aya wishes to color $k$ cells of this table so that that there is a unique way to place $n$ tokens on colored squares without two tokens are not in the same row or column. What is the maximum value of $k$ for which Aya's wish is achievable?
Claim: The maximum for $k$ is $\frac{n(n+1)}{2}$.
Proof:
A possible construction is: Take one of the large diagonals of the table, and color every cell above and on that diagonal.
Proof that this is optimal:
Take a possible arrangement and consider the colored cells with tokens.
Main Idea (Lemma): There cannot be a rectangle in the table such that all its vertices are colored cells and two diagonal vertices have tokens. Otherwise, one could just move the tokens to the other two vertices and we would have another arrangement of the tokens.
For every choice of two tokens, consider the two cells that form a rectangle together with the two tokens.
Using the Lemma, we get that one of them must be uncolored. Since there are $\frac{n(n-1)}{2}$ pairs of tokens that form disjoint rectangles, there are at least $\frac{n(n-1)}{2}$ uncolored cells.