The least possible number of tokens on a $n×n$ board Tokens are placed on the squares of a
$2021
×
2021$
board in such a way that each square contains at most one token. The token set of a square of the board is the collection of all tokens which are in the same row or column as this square. (A token belongs to the token set of the square in which it is placed.) What is the least possible number of tokens on the board if no two squares have the same token set?.
It's a problem from https://gonitzoggo.com/archive/problem/441/english Recently, I've been taking preparation for junior Math Olympiad Contest and found this problem.
I have calculated least possible number of tokens for $ 2×2, 3×3, 4×4, 5×5$ but finding no pattern between them.
 A: We’ll show that TonyK’s construction of $\left\lfloor \frac{3n}2\right\rfloor$ tokens on an $n × n$ board is minimal for $n ≥ 2$ (for $n = 1$, the empty board is better).  This is clear for $n = 2$; suppose $n ≥ 3$.
If column $a$ is empty, then there must be at least two tokens in each column $b ≠ a$ (because if there are zero or one at $(b, c)$, then $(a, c)$ and $(b, c)$ have the same token set), for at least $2(n - 1) ≥ \left\lfloor \frac{3n}2\right\rfloor$ tokens.  Similarly if row $a$ is empty.
Otherwise, there are no empty rows or columns.  Among the tokens that are the only token in their row, no two can share a column (because they’d have the same token set), so at most $n$ tokens are the only token in their row or the only token in their column.  Furthermore, at most one of these is the only token in its row and column (because if there were two at $(a, b)$ and $(c, d)$, then $(a, d)$ and $(b, c)$ would have the same token set)).  That leaves at least $n - 1$ of the $2n$ rows and columns that must have multiple tokens.  So either at least $\left\lceil\frac{n - 1}{2}\right\rceil$ rows have multiple tokens, or at least $\left\lceil\frac{n - 1}{2}\right\rceil$ columns have multiple tokens; either way, this accounts for at least $n + \left\lceil\frac{n - 1}{2}\right\rceil = \left\lfloor\frac{3n}{2}\right\rfloor$ tokens.
A: On an $N\times N$ board, we can do this with $\frac32N$ tokens if $N$ is even: fill the main diagonal with tokens, and a parallel sub-diagonal of length $\frac12N$. And if $N$ is odd, we only need $\frac12(3N-1)$ tokens, because the parallel sub-diagonal can be of length $\frac12(N-1)$. For example ($N=10$ and $N=11$):
$$
\begin{bmatrix}
\bullet & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot \\
\cdot & \bullet & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot \\
\cdot & \cdot & \bullet & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot \\
\cdot & \cdot & \cdot & \bullet & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot \\
\cdot & \cdot & \cdot & \cdot & \bullet & \cdot & \cdot & \cdot & \cdot & \cdot \\
\bullet & \cdot & \cdot & \cdot & \cdot & \bullet & \cdot & \cdot & \cdot & \cdot \\
\cdot & \bullet & \cdot & \cdot & \cdot & \cdot & \bullet & \cdot & \cdot & \cdot \\
\cdot & \cdot & \bullet & \cdot & \cdot & \cdot & \cdot & \bullet & \cdot & \cdot \\
\cdot & \cdot & \cdot & \bullet & \cdot & \cdot & \cdot & \cdot & \bullet & \cdot \\
\cdot & \cdot & \cdot & \cdot & \bullet & \cdot & \cdot & \cdot & \cdot & \bullet \\
\end{bmatrix}
\,\,\,\,\,\,\,\,\,\,\,\,
\begin{bmatrix}
\bullet & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot \\
\cdot & \bullet & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot \\
\cdot & \cdot & \bullet & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot \\
\cdot & \cdot & \cdot & \bullet & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot \\
\cdot & \cdot & \cdot & \cdot & \bullet & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot \\
\cdot & \cdot & \cdot & \cdot & \cdot & \bullet & \cdot & \cdot & \cdot & \cdot & \cdot \\
\bullet & \cdot & \cdot & \cdot & \cdot & \cdot & \bullet & \cdot & \cdot & \cdot & \cdot \\
\cdot & \bullet & \cdot & \cdot & \cdot & \cdot & \cdot & \bullet & \cdot & \cdot & \cdot \\
\cdot & \cdot & \bullet & \cdot & \cdot & \cdot & \cdot & \cdot & \bullet & \cdot & \cdot \\
\cdot & \cdot & \cdot & \bullet & \cdot & \cdot & \cdot & \cdot & \cdot & \bullet & \cdot \\
\cdot & \cdot & \cdot & \cdot & \bullet & \cdot & \cdot & \cdot & \cdot & \cdot & \bullet \\
\end{bmatrix}
$$
So if $N=2021$, there exists an arrangment of $3031$ tokens in which no two squares have the same token set.
I have checked on my laptop that these arrangements are the best possible for $N\le 7$, but for $N\ge 8$ I don't have any kind of proof.
