\documentclass[11pt]{scrartcl}
\usepackage{evan}

\begin{document}
\title{USAMO 2020/2}
\subtitle{Evan Chen}
\author{Twitch Solves ISL}
\date{Episode 16}
\maketitle

\section*{Problem}
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 \emph{beam} is a $1 \times 1 \times 2020$ rectangular prism.
Several beams are placed inside the cube subject to the following conditions:
\begin{itemize}
\item 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.)
\item No two beams have intersecting interiors.
\item 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.
\end{itemize}
What is the smallest positive number of beams that can be placed to satisfy these conditions?

\section*{Video}
\href{https://www.youtube.com/watch?v=r7j0oRtpErA&t=2440}{\texttt{https://youtu.be/r7j0oRtpErA}}

\section*{External Link}
\url{https://aops.com/community/p15952773}

\newpage

\section*{Solution}
\paragraph{Answer.} $3030$ beams.

\paragraph{Construction.}
We first give a construction with $3n/2$ beams for any $n \times n \times n$ box,
where $n$ is an even integer.
Shown below is the construction for $n=6$, which generalizes.
(The left figure shows the cube in 3d;
the right figure shows a direct view of the three visible faces.)
\begin{center}
\begin{asy}
import three;
import bsp;

size(8cm);
settings.prc = false;
settings.render = 0;
settings.tex="pdflatex";
settings.outformat="pdf";

triple O = (9,7,5);
currentprojection = orthographic(O);
currentlight = light(gray(2),specular=gray(0.7), specularfactor=3, (7,7,5));

pen finalpen = yellow+2;
pen meshpenlight = rgb(0.95,0.95,0.99);

int M = 6;
int s = 0;
for (int i=0; i<=M; ++i) {
draw( (s,i,0)--(s,i,M), meshpenlight);
draw( (s,0,i)--(s,M,i), meshpenlight);
draw( (i,s,0)--(i,s,M), meshpenlight);
draw( (0,s,i)--(M,s,i), meshpenlight);
draw( (i,0,s)--(i,M,s), meshpenlight);
draw( (0,i,s)--(M,i,s), meshpenlight);
}

draw(box((0,0,0), (M,M,M)), finalpen);

pen penA = red;
pen penB = cyan;
pen penC = green;

draw(shift(0,0,0)*unitcube, penA);
draw(shift(0,0,1)*unitcube, penA);
draw(shift(0,0,2)*unitcube, penA);
draw(shift(0,0,3)*unitcube, penA);
draw(shift(0,0,4)*unitcube, penA);
draw(shift(0,0,5)*unitcube, penA);

draw(shift(1,0,0)*unitcube, penB);
draw(shift(1,1,0)*unitcube, penB);
draw(shift(1,2,0)*unitcube, penB);
draw(shift(1,3,0)*unitcube, penB);
draw(shift(1,4,0)*unitcube, penB);
draw(shift(1,5,0)*unitcube, penB);

draw(shift(0,1,1)*unitcube, penC);
draw(shift(1,1,1)*unitcube, penC);
draw(shift(2,1,1)*unitcube, penC);
draw(shift(3,1,1)*unitcube, penC);
draw(shift(4,1,1)*unitcube, penC);
draw(shift(5,1,1)*unitcube, penC);

draw(shift(2,2,0)*unitcube, penA);
draw(shift(2,2,1)*unitcube, penA);
draw(shift(2,2,2)*unitcube, penA);
draw(shift(2,2,3)*unitcube, penA);
draw(shift(2,2,4)*unitcube, penA);
draw(shift(2,2,5)*unitcube, penA);

draw(shift(3,0,2)*unitcube, penB);
draw(shift(3,1,2)*unitcube, penB);
draw(shift(3,2,2)*unitcube, penB);
draw(shift(3,3,2)*unitcube, penB);
draw(shift(3,4,2)*unitcube, penB);
draw(shift(3,5,2)*unitcube, penB);

draw(shift(0,3,3)*unitcube, penC);
draw(shift(1,3,3)*unitcube, penC);
draw(shift(2,3,3)*unitcube, penC);
draw(shift(3,3,3)*unitcube, penC);
draw(shift(4,3,3)*unitcube, penC);
draw(shift(5,3,3)*unitcube, penC);

draw(shift(4,4,0)*unitcube, penA);
draw(shift(4,4,1)*unitcube, penA);
draw(shift(4,4,2)*unitcube, penA);
draw(shift(4,4,3)*unitcube, penA);
draw(shift(4,4,4)*unitcube, penA);
draw(shift(4,4,5)*unitcube, penA);

draw(shift(5,0,4)*unitcube, penB);
draw(shift(5,1,4)*unitcube, penB);
draw(shift(5,2,4)*unitcube, penB);
draw(shift(5,3,4)*unitcube, penB);
draw(shift(5,4,4)*unitcube, penB);
draw(shift(5,5,4)*unitcube, penB);

draw(shift(0,5,5)*unitcube, penC);
draw(shift(1,5,5)*unitcube, penC);
draw(shift(2,5,5)*unitcube, penC);
draw(shift(3,5,5)*unitcube, penC);
draw(shift(4,5,5)*unitcube, penC);
draw(shift(5,5,5)*unitcube, penC);

pen meshpen = grey;
int s = M;
for (int i=1; i<=M-1; ++i) {
draw( (s,i,0)--(s,i,M), meshpen);
draw( (s,0,i)--(s,M,i), meshpen);
draw( (i,s,0)--(i,s,M), meshpen);
draw( (0,s,i)--(M,s,i), meshpen);
draw( (i,0,s)--(i,M,s), meshpen);
draw( (0,i,s)--(M,i,s), meshpen);
}

draw((M,M,M)--(0,M,M), finalpen);
draw((M,M,M)--(M,0,M), finalpen);
draw((M,M,M)--(M,M,0), finalpen);
\end{asy}
\quad
\begin{asy}
size(8cm);
picture redface, greenface, blueface;

void draw_grid(picture pic) {
  for (int i=1; i<6; ++i) {
    draw(pic, (i,0)--(i,6), grey);
    draw(pic, (0,i)--(6,i), grey);
  }
  draw(pic, scale(6)*unitsquare, yellow+2);
}

fill(redface, shift(0,5)*unitsquare, red);
fill(redface, shift(2,3)*unitsquare, red);
fill(redface, shift(4,1)*unitsquare, red);
draw_grid(redface);

fill(greenface, shift(5,5)*unitsquare, green);
fill(greenface, shift(3,3)*unitsquare, green);
fill(greenface, shift(1,1)*unitsquare, green);
draw_grid(greenface);

fill(blueface, shift(0,4)*unitsquare, cyan);
fill(blueface, shift(2,2)*unitsquare, cyan);
fill(blueface, shift(4,0)*unitsquare, cyan);
draw_grid(blueface);

add(shift(0,8.5)*shift(3,3)*rotate(-45)*shift(-3,-3)*redface);
add(shift(-4,0)*greenface);
add(shift( 4,0)*blueface);
label("Left face", (-1,0), dir(-90));
label("Right face", (7,0), dir(-90));
label("Top face", (3,16), dir(90));
\end{asy}
\end{center}
To be explicit,
impose coordinate axes such that one corner of the cube is the origin.
We specify a beam by two opposite corners.
The $3n/2$ beams come in three directions, $n/2$ in each direction:
\begin{itemize}
  \ii $(0,0,0) \to (1,1,n)$, $(2,2,0) \to (3,3,n)$, $(4,4,0) \to (5,5,n)$, and so on;
  \ii $(1,0,0) \to (2,n,1)$, $(3,0,2) \to (4,n,3)$, $(5,0,4) \to (6,n,5)$, and so on;
  \ii $(0,1,1) \to (n,2,2)$, $(0,3,3) \to (n,4,4)$, $(0,5,5) \to (n,6,6)$, and so on.
\end{itemize}
This gives the figure we drew earlier and shows $3030$ beams is possible.

\paragraph{Necessity.}
We now show at least $3n/2$ beams are necessary.
Maintain coordinates, and call the beams $x$-beams, $y$-beams, $z$-beams
according to which plane their long edges are perpendicular too.
Let $N_x$, $N_y$, $N_z$ be the number of these.

\begin{claim*}
  If $\min(N_x, N_y, N_z) = 0$, then at least $n^2$ beams are needed.
\end{claim*}
\begin{proof}
  Assume WLOG that $N_z = 0$.
  Orient the cube so the $z$-plane touches the ground.
  Then each of the $n$ layers of the cube (from top to bottom)
  must be completely filled, and so at least $n^2$ beams are necessary,
\end{proof}

We henceforth assume $\min(N_x, N_y, N_z) > 0$.

\begin{claim*}
  If $N_z > 0$, then we have $N_x + N_y \ge n$.
\end{claim*}
\begin{proof}
  Again orient the cube so the $z$-plane touches the ground.
  We see that for each of the $n$ layers of the cube (from top to bottom),
  there is at least one $x$-beam or $y$-beam.
  (Pictorially, some of the $x$ and $y$ beams form a ``staircase''.)
  This completes the proof.
\end{proof}
Proceeding in a similar fashion, we arrive at the three relations
\begin{align*}
  N_x + N_y &\ge n \\
  N_y + N_z &\ge n \\
  N_z + N_x &\ge n.
\end{align*}
Summing gives $N_x  + N_y + N_z \ge 3n/2$ too.

\begin{remark*}
  The problem condition has the following ``physics'' interpretation.
  Imagine the cube is a metal box which is sturdy enough that
  all beams must remain orthogonal to the faces of the box
  (i.e.\ the beams cannot spin).
  Then the condition of the problem is exactly what is needed so that,
  if the box is shaken or rotated, the beams will not move.
\end{remark*}

\begin{remark*}
  Walter Stromquist points out that the number of constructions
  with $3030$ beams is actually enormous:
  not dividing out by isometries,
  the number is $(2 \cdot 1010!)^3$.
\end{remark*}

\end{document}
