2020 USOJMO Problems/Problem 3
Problem
An empty cube is given, and a
grid of square unit cells is drawn on each of its six faces. A
is a
rectangular prism. Several beams are placed inside the cube subject to the following conditions:
- The two faces of each beam coincide with unit cells lying on opposite faces of the cube. (Hence, there are
possible positions for a beam.)
- No two beams have intersecting interiors.
- The interiors of each of the four 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?
Solution
Place the cube in the xyz-coordinate, with the positive x-axis pointing forward, the positive y-axis pointing right, and the positive z-axis pointing up. Let the position of a unit cube be if it is centered at
. Place the
cube so that the edges are parallel to the axes, and two of its corners are at
and
. Now call a beam z-oriented if its endpoints differ only in z-coordinates, and similarly call it x-oriented or y-oriented if the endpoints differ in x- or y-coordinates, respectively.
We claim that the answer is . First we will prove 3030 suffices. Place the first beam so its endpoints lie at
, and
. Place the 2nd beam so its endpoints lie at
and
. Place the 3rd beam so its endpoints lie at
and
. Now it is clear that the only faces among these three beams that are not touching the faces of the
cube of the face of another beam are the top face of beam 2, and the front and right faces of beam 3.
Now place the 4th beam from to
, 2 units up and right of beam 1. Then place beam 5 from
to
, 2 units forward and up of beam 2. Place beam 6 from
to
, 2 unites forward and right of beam 3. Note that these 3 beams will touch the top face of beam 2, and the front and right faces of beam 3. Now the only faces that are not touching another face are the top of beam 5, and the front and right of beam 6.
We can repeat this process 1010 times, placing the beams in groups of 3 so that beam is 2 units up and right of beam
, beam
is 2 units forward and up of beam
, and beam
is 2 units forward and right of beam
, for all
. After placing each set of 3 as such, the faces of the previous beams will all satisfy condition 3. And for the last set of 3 (that is, beams 3028, 3029, and 3030), their faces will satisfy condition 3 as well, since the top face of beam 3029 and the front/right faces of beam 3030 will touch the cube (again, note that all other faces will be touching another beam).
Thus, we have shown that 3030 beams suffices, so we will now show that 3030 beams is the minimum. Let there be x-oriented beams,
y-oriented beams, and
z-oriented beams. Now look each
slice of the cube, parallel to the xz-plane. Note there are 2020 such slices. There are two cases. Either
, or at least one of A or C is nonzero. In the first case, we clearly have at least
beams as desired. In the second case, we must have at least one beam in each
slice, in order to satisfy condition 3. If there is some slice without a beam, then there will be some x- or z-oriented beam with no beams touching its top or bottom face. Additionally, notice that only x- or z-oriented beams can fit in a
slice, so
. Similarly, we must have
,
, or both
and
. In every case, the number of beams,
, will be at least 3030 as desired.
~MortemEtInteritum