2. We have $n^{2}$ empty boxes; each of them has a square base. The height and width of each box are natural numbers from the set $\{1,2, \ldots, n\}$. Any two boxes differ in at least one of these two dimensions. One box can be placed inside another if both dimensions are smaller, and at least one of the dimensions is at least 2 smaller. Thus, we can create a sequence of boxes nested inside each other (i.e., the first box is inside the second, the second box is inside the third, etc.). Each such set will be stored on a different shelf. Determine the smallest possible number of shelves needed $k$ to store all $n^{2}$ boxes.
SOLUTION. We will show that the sought minimum number of shelves is equal to $3n-2$. This answer is clearly correct for $n=1$ and for $n=2$, since for such $n$ it holds that $n^2 = 3n-2$ and at the same time each of the $n^2$ boxes must be obviously stored on a different shelf. For the rest of the solution, we will therefore assume that $n \geq 3$.

We will assign a table $n \times n$ to the boxes - a box with width $w$ and height $h$ will correspond to a point with coordinates $(w, h)$ in it.

No two boxes from the set $S=\{(w, h): n \leq w+h \leq n+2\}$ (the three longest diagonals, see Fig. 1 for $n=7$) can be on the same shelf. If $(w, h)$ and $\left(w', h'\right)$ are two boxes on the same shelf, for which $w < w'$ and $h < h'$, then $w+1 \leq w'$ and $h+1 \leq h'$, and at the same time $w+2 \leq w'$ or $h+2 \leq h'$. In both cases, we get by adding $w+h+3 \leq w'+h'$. If, therefore, $(w, h) \in S$, then $w'+h' \geq w+h+3 \geq n+3$, so $\left(w', h'\right) \notin S$. Since $|S|=3n-2$, there must be at least $3n-2$ shelves.

![](https://cdn.mathpix.com/cropped/2024_04_17_7615e536344b62b2b1b3g-02.jpg?height=526&width=505&top_left_y=1256&top_left_x=433)

Fig. 1

![](https://cdn.mathpix.com/cropped/2024_04_17_7615e536344b62b2b1b3g-02.jpg?height=526&width=505&top_left_y=1256&top_left_x=1118)

Fig. 2

Now we will show how to divide the boxes into shelves so that $3n-2$ shelves are sufficient. A possible procedure for $n=7$ is evident from Fig. 2 (sets of nested boxes are marked with arrows) and can be directly generalized to the case of any $n \geq 3$. In that case, we will put two boxes $(w, h)$ and $\left(w', h'\right)$ on the same shelf if and only if $2(h'-h) = w'-w$. In other words, we start with the "largest" boxes $(n-1, h), (n, h)$ for $h=1,2, \ldots, n$ and $(w, n)$ for $w=1,2, \ldots, n-2$ and place each of these $3n-2$ boxes on a separate shelf. Then, on each shelf, we perform the following algorithm: We look at the last box placed on the shelf, let it be $(w, h)$. If $w-2 \geq 1$ and $h-1 \geq 1$, we add the box $(w-2, h-1)$ to the shelf (i.e., we nest it inside the box on the shelf) and repeat the step of the algorithm (otherwise, we stop). The given rules are trivially satisfied for each shelf. The value $3n-2$ is therefore indeed achievable.

It remains to explain why each of the $n^2$ boxes is stored on some shelf. For a given box $(w, h)$, we determine the shelf on which it will end up by gradually increasing $w$ by 2 and $h$ by 1 until we finally get one of the $3n-2$ largest initial boxes with width $w \in \{n-1, n\}$ or height $h=n$. During this process of increasing, we get a sequence of nested boxes stored on the shelf, which we initially assigned to the mentioned largest box. The number $3n-2$ of boxes is therefore indeed sufficient.

Note. It is interesting that there are also other valid arrangements of all $n^2$ boxes with the same set of $3n-2$ largest boxes in individual shelves that we used in our solution - for $n=7$, one such different arrangement is shown in Fig. 3.

![](https://cdn.mathpix.com/cropped/2024_04_17_7615e536344b62b2b1b3g-03.jpg?height=531&width=512&top_left_y=534&top_left_x=772)

Fig. 3

SUPPLEMENTARY AND ADDITIONAL PROBLEMS:

N1. Two squares on a chessboard are called adjacent if they share a side. How many squares can be selected on a chessboard $2n \times 2n$ so that no two of the selected squares are adjacent? [Half. The entire chessboard can be divided into disjoint pairs of adjacent squares, and from each pair, we can select at most one square. Half can be achieved, for example, by selecting all squares of one color in the classic chessboard coloring.]

N2. Solve the given problem for $n=4$ and $n=5$. It is not enough to guess the minimum number of shelves: it is necessary to show both that it is possible to store the boxes on the specified number of shelves and to justify that a smaller number of shelves will not be sufficient.

N3. For $n \in \{3,4\}$, find the largest set of boxes such that none of them can be nested inside another. Try to generalize your set for larger $n$.

D1. An excellent supplementary material (suitable for independent preparation of students) is Chapter 3.2 in the KMS Collection available at http://kms.sk/zbierka.