Pebbles are placed on a $2021 \times 2021$ board in such a way that each square contains at most one pebble. The pebble set of a square of the board is the collection of all pebbles which are in the same row or column as this square. Determine the least number of pebbles that can be placed on the board in such a way that no two squares have the same pebble set.
Let \( N \geqslant 1 \) be a positive integer. We claim that the least number of pebbles that can be placed on a \((2 N+1) \times (2 N+1)\) chessboard in such a way that no two squares of the board have the same pebble set is \(3 N+1\). The problem has \(N=1010\), so at least 3031 pebbles are needed.

We begin by placing \((2 N+1) + N = 3 N + 1\) pebbles on the board as shown. The construction extends to all values of \(N\), and one checks that no two squares on the board have the same pebble set.
![](https://cdn.mathpix.com/cropped/2024_04_17_e159f221721784e79019g-4.jpg?height=354&width=966&top_left_y=1174&top_left_x=545)

We are left to show that the number of pebbles, \(P\), that must be placed on the board is at least \(3 N + 1\). Suppose that there exists an empty row. Any other row must then contain at least two pebbles. Indeed, if another row is empty, Figure [1], or contains exactly one pebble, Figure [2], then there are two squares (shaded in the figures below) with the same pebble set. So in this case there are at least \(P \geqslant 2(2 N + 1 - 1) = 4 N \geqslant 3 N + 1\) pebbles on the board. The same argument applies, mutatis mutandis, to the columns of the board.

[1]

![](https://cdn.mathpix.com/cropped/2024_04_17_e159f221721784e79019g-4.jpg?height=243&width=271&top_left_y=1900&top_left_x=344)

[2]

![](https://cdn.mathpix.com/cropped/2024_04_17_e159f221721784e79019g-4.jpg?height=254&width=257&top_left_y=1889&top_left_x=748)

[3]

![](https://cdn.mathpix.com/cropped/2024_04_17_e159f221721784e79019g-4.jpg?height=229&width=263&top_left_y=1913&top_left_x=1136)

[4]

![](https://cdn.mathpix.com/cropped/2024_04_17_e159f221721784e79019g-4.jpg?height=266&width=274&top_left_y=1877&top_left_x=1528)

On the other hand, suppose that each row and each column contains at least one pebble. Let \(k\) be the number of rows containing precisely one pebble. Counting the number of pebbles per row shows that \(P \geqslant k + 2(2 N + 1 - k)\). To count the number of pebbles per column, note that the \(k\) pebbles that are the only ones in their row must be in \(k\) distinct columns, Figure [3]. Furthermore, at most one of these \(k\) columns only has one pebble in it, Figure [4]. So these \(k\) columns contain a total of at least \(2 k - 1\) pebbles, while the remaining columns contain at least one each. Hence \(P \geqslant (2 k - 1) + (2 N + 1 - k)\). Adding these two inequalities we get \(2 P \geqslant 6 N + 2\).

Remark. For a \(2 N \times 2 N\) board, at least \(3 N\) pebbles are needed. The proof is similar: if there is an empty line, then \(P \geqslant 2(2 N - 1) \geqslant 3 N\) for \(N \geqslant 2\). If there is no empty line, then \(2 P \geqslant 6 N - 1\). A construction similar to that of the odd boards works. While the construction is unique in the odd case, up to permutation of rows and columns, that is not true for even boards.