3
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ The question is not quite clear. The tokens belong to some set I suppose (it does not matter much which as long as it is large enough) but it is not stated whether all placed tokens need to be distinct, and if not whether tokens are counted with multiplicity for the "number of tokens" used. If they are counted with multiplicity; it would appear to never be advantageous to use a same token mre than once. $\endgroup$ Jul 30, 2022 at 15:50
  • 2
    $\begingroup$ Please tell us the result of your calculations! $\endgroup$
    – TonyK
    Jul 30, 2022 at 15:54
  • $\begingroup$ @MarcvanLeeuwen: The question seems clear to me. It doesn't matter whether the tokens are distinguishable or not. If you want to make it explicit, you can regard the token set of a square as the set of squares in the same row or column that contain a token. $\endgroup$
    – TonyK
    Jul 30, 2022 at 20:52

2 Answers 2

5
+100
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ "So at most $n+1$ of the $2n$ rows and columns have only one token": this is not obvious to me. I'm sure you are right, but I feel that your argument is missing a step here. $\endgroup$
    – TonyK
    Aug 4, 2022 at 11:25
  • $\begingroup$ @TonyK I’ve clarified that step. $\endgroup$ Aug 4, 2022 at 16:42
4
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Now I got it. Thanks a lot! @TonyK $\endgroup$ Jul 31, 2022 at 17:19

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .