66th Czech and Slovak Mathematical Olympiad

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^{\prime },h^{\prime })$ are on the same shelf and $w<w^{\prime },h<h^{\prime }$. Then $w+1\le w^{\prime },h+1\le h^{\prime }$, and either $w+2\le w^{\prime }$ or $h+2\le h^{\prime }$. Either way, summing up we obtain $w+h+3\le w^{\prime }+h^{\prime }$.

Fig. 1 Fig. 2 If $(w,h)\in S$ then $w^{\prime }+h^{\prime }\ge w+h+3\ge n+3$, hence $(w^{\prime },h^{\prime })\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^{\prime },h^{\prime })$ are put on the same shelf if and only if $2(h^{\prime }-h)=w^{\prime }-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.