USOMO 2020 Problem 2

An empty $2020 \times 2020 \times 2020$ cube is given, and a $2020 \times 2020$ grid of square unit cells is drawn  on each of its six faces. A beam is a $1 \times 1 \times 2020$ rectangular prism. Several beams are placed inside the cube subject to the following conditions:

-- The two $1 \times 1$ faces of each beam coincide with unit cells lying on opposite faces of the cube. (Hence, there are $3 \cdot {2020}^2$ possible positions for a beam.)
-- No two beams have intersecting interiors.
-- The interiors of each of the four $1 \times 2020$ faces of each beam touch either a face of the cube or the interior of the face of another beam.

What is the smallest positive number of beams that can be placed to satisfy these conditions?

This one is easy!

Solution:

We prove it's $3n/2$ for every even $n$, i.e. $3030$ for $n=2020$, followed by construction.

Let $S$ be the set of minimum number of beams. Define a layer as a set of horizontally or vertically adjacent $n^2$ unit cubes. There are $3n$ layers. Consider the $n$ horizontal layers. Either each of them contains a beam in $S$, or none of them does and $S$ consists of $n^2$ vertical beams.

If nothing like the latter case happens in any direction, then each of the $3n$ layers contains a beam in $S$. Every beam is contained in exactly $2$ layers, so $S$ has at least $3n/2$ beams. It could be easily constructed. If the latter case happens in some direction, then $S$ has $n^2$ beams, more than $3n/2$ and so not the minimum.