Problem 2013

We will show that the required minimal number of shelves is $3n-2$. This answer is clearly correct for $n=1$ and $n=2$ since for such $n$ we have $n^2 = 3n - 2$ and each box has to be stored on a different shelf. From now on, let $n \ge 3$.
We identify boxes with points in an $n \times n$ grid: A box of width $w$ and height $h$ corresponds to point with coordinates $(w, h)$.
No two boxes from the set $S = \{(w,h): n \le w+h \le n+2\}$ (three longest diagonals, see Fig. 1 for $n=7$) can be on the same shelf: Indeed, Assume $(w,h)$ and $(w',h')$ are on the same shelf and $w < w', h < h'$. Then $w+1 \le w', h+1 \le h'$, and either $w+2 \le w'$ or $h+2 \le h'$. Either way, summing up we obtain $w+h+3 \le w'+h'$.

Fig. 1

Fig. 2
If $(w, h) \in S$ then $w' + h' \ge w + h + 3 \ge n + 3$, hence $(w', h') \notin S$. As $|S| = 3n - 2$, we need at least $3n - 2$ shelves.
Now we show how to split the boxes so that $3n-2$ shelves are enough. A possible way for $n=7$ is clear from Fig. 2 (the sequences of boxes stored inside one another are illustrated by arrows) and it can be directly generalised to any $n \ge 3$. Two boxes $(w, h)$, $(w', h')$ are put on the same shelf if and only if $2(h' - h) = w' - w$. In other words, we start with “largest” boxes $(n-1, h)$, $(n, h)$ for $h = 1, 2, \dots, n$ and $(w, n)$ for $w = 1, 2, \dots, n-2$, and we put each of these $3n-2$ boxes on a different shelf. Then we follow the following algorithm on each shelf: Assume the last box put on the shelf is $(w, h)$. If $w-2 \ge 1$ and $h-1 \ge 1$, we add box $(w-2, h-1)$ to the shelf (inside the previous box) and repeat this step; otherwise we end. Obviously, the arrangement of boxes on every shelf satisfies the requirements. Moreover, each box is stored on exactly one shelf: To identify it, keep increasing $w$ by 2 and $h$ by 1 (simultaneously) until $w \in \{n-1, n\}$ or $h = n$. Thus $3n-2$ shelves are also sufficient.