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? Proposed by Alex Zhai
Problem
Source: USOMO 2020 Problem 2, USOJMO 2020 Problem 3
Tags: AMC, USA(J)MO, geometry, 3D geometry, Hi
22.06.2020 02:00
We claim the answer is $3030$. A shaded square represents a beam with one end at that square. The construction for $8$, which easily generalizes, is shown below: [asy][asy] for (real i = 0; i <= 8; i+=1) { draw((i,0)--(i,8)--(i+4sqrt(3),12)); draw((0,i)--(8,i)--(8+4sqrt(3),i+4)); draw((i*sqrt(3)/2,8+i/2)--(8+i*sqrt(3)/2,8+i/2)--(8+i*sqrt(3)/2,i/2)); } for (real j = 0; j<=3; j+=1) { fill((2j+1,7-2j)--(2j+2,7-2j)--(2j+2,8-2j)--(2j+1,8-2j)--cycle); fill((j*sqrt(3)+2j,8+j)--(j*sqrt(3)+2j+1,8+j)--(j*sqrt(3)+2j+1+sqrt(3)/2,8.5+j)--(j*sqrt(3)+2j+sqrt(3)/2,8.5+j)--cycle); fill((8+sqrt(3)/2+j*sqrt(3),7.5-j)--(8+sqrt(3)+j*sqrt(3),8-j)--(8+sqrt(3)+j*sqrt(3),7-j)--(8+sqrt(3)/2+j*sqrt(3),6.5-j)--cycle); } [/asy][/asy] (sorry for the ugly cube) We now prove at least $3030$ beams are needed. Call a beam to be an $x$-beam, a $y$-beam, or a $z$-beam if it is parallel to the $x,y,$ or $z$ axis respectively. Call a $1 \times 2020 \times 2020$ block a slab, and call a slab an $xy$-slab, a $yz$-slab, or an $zx$-slab if it is parallel to the $xy$ plane, the $yz$ plane, or the $zx$ plane respectively. I claim that ever slab must contain at least one beam fully inside of it. Note that if all beams are of one type, then $2020^2>3030$ beams are required. Thus, assume at least $2$ different types of beams are use, without loss of generality say an $x$-beam and a $y$-beam are used. Look at a particular $x$-beam. It is inside of a $xy$-slab, call this slab $\mathcal{S}$. The two slabs (possibly one if $\mathcal{S}$ touches a face of the cube) adjacent to $\mathcal{S}$ must fully contain a beam, otherwise two of the faces of the chosen $x$-beam cannot be covered. We may induct in both directions to show that every $xy$-slab must contain at least one beam fully inside of it. Similarly, we can say the same thing for $xz$-slabs. We can look at a $y$-beam and say the same thing about $yz$-slabs. Thus, the claim is proven. Note that every beam is inside exactly two slabs. Thus: $$2\times [\text{number of beams}] \geq [\text{number of slabs with a beam inside}] = 3 \times 2020 = 6060,$$meaning at least $3030$ beams are required, as claimed.
22.06.2020 02:01
I claim the answer is $\boxed{3030}$. A construction is as follows: consider the following labeling of the edges for the cube. [asy][asy] pen red=rgb(1,0,0); pen green=rgb(0,1,0); pen blue=rgb(0,0,1); draw((0,0)--(10,0)); draw((10,0)--(10,10),red); draw((10,10)--(0,10),green); draw((0,10)--(0,0)); draw((0,10)--(4,13),blue); draw((4,13)--(14,13)--(10,10)); draw((10,0)--(14,3), blue); draw((14,3)--(14,13)); draw((0,0)--(4,3)); draw((4,3)--(4,13), red); draw((4,3)--(14,3), green); dot((0,0)); dot((0,10)); dot((10,10)); dot((10,0)); dot((4,3)); dot((14,3)); dot((14,13)); dot((4,13)); label("a", (2,11.5), NW, blue); label("b", (12, 1.5), SE,blue); label("d", (6.5,10), N,green); label("c", (7,3), N,green); label("e",(10,7), E,red); label("f",(4,7), W,red); [/asy][/asy] Lay one beam with one of its long edges coinciding with $a$, and place $1009$ other beams in the same orientation diagonally from $a$ to $b$, evenly spaced apart. If we were to consider the $2020\times 2020$ grid of unit squares formed by the beams, with squares shaded in if there were a beam, it would look like the long diagonal of an $n\times n$ chessboard, with $n$ even (hence, there is no beam sharing a long edge with $b$). Place $1010$ beams similarly from $c$ to $d$ and from $e$ to $f$, and it's easy to see this construction works by considering beams of two different orientations at a time. I will now show that $3030$ is necessary. Suppose all the beams were in the same orientation. Then, the entire cube must be filled or else there will exist a beam that has one of its faces exposed, giving $2020^2$ beams. Now suppose that all the beams are not in the same orientation. By Pigeonhole, for each set of parallel faces of the cube there exists at least one beam whose $1\times 2020$ side is parallel to each of the faces. The main claim is that if for each set of parallel faces we split the cube into $2020$ $1\times 2020\times 2020$ rectangular prisms with the $2020\times 2020$ faces of each prism parallel to the set of parallel faces of the cube, there must exist at least one beam in each prism. If not, then, similar to the all same orientation case, there will exist a beam whose face is exposed, contradiction. Thus, for each set of parallel faces on the cube, there must exist at least $2020$ beams whose $1\times 2020$ faces are parallel to these faces. Now suppose there are $x$ beams running parallel to the edge labelled $a$, $y$ beams parallel to $c$, and $z$ beams parallel to $e$, meaning we have $x+y+z$ total beams. Using the claim, we have the following set of inequalities: \[x+y\geq 2020\]\[y+z\geq 2020\]\[z+x\geq 2020\]where each inequality corresponds to the appropriate set of parallel faces on the cube. Summing these and dividing by two gives $x+y+z\geq 3030$, as claimed.
22.06.2020 02:03
Here’s a solution which sorta outlines my motivation. I had trumpeter on my mind while writing it up, idk if it affected anything.
Attachments:

22.06.2020 02:05
pretty easy for a #2, except for the writeup
22.06.2020 04:11
Proposed by Alex Zhai
22.06.2020 04:24
if this was on the AIME i probably would've solved it lol
22.06.2020 04:50
Answer: $3030$ beams. \medskip 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.) [asy][asy] import three; import bsp; size(8cm); settings.prc = false; settings.render = 0; 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); [/asy][/asy] [asy][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)); [/asy][/asy] 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: $(0,0,0) \to (1,1,n)$, $(2,2,0) \to (3,3,n)$, $(4,4,0) \to (5,5,n)$, and so on; $(1,0,0) \to (2,n,1)$, $(3,0,2) \to (4,n,3)$, $(5,0,4) \to (6,n,5)$, and so on; $(0,1,1) \to (n,2,2)$, $(0,3,3) \to (n,4,4)$, $(0,5,5) \to (n,6,6)$, and so on. This gives the figure we drew earlier and shows $3030$ beams is possible. \bigskip 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. Claim: If $\min(N_x, N_y, N_z) = 0$, then at least $n^2$ beams are needed. 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, $\blacksquare$ We henceforth assume $\min(N_x, N_y, N_z) > 0$. Claim: If $N_z > 0$, then we have $N_x + N_y \ge n$. 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. $\blacksquare$ 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. 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.
22.06.2020 05:36
only if i didnt spend 3 hours on #2 and didnt solve it >
22.06.2020 05:45
how many points should a correct proof of lower bound 3030 but an incorrect construction expect?
22.06.2020 05:58
The answer is $3030$. Let $n=2020$. As 3D is hard on a paper, we will do everything in terms of coordinates. Give the coordinate of the cubes $(x,y,z)$ where $1\leq x,y,z\leq n$. We will parameterize the beams as $(x,y,*)$, $(*,y,z)$ or $(x,*,z)$ depending on its direction. Construction: We give the following set $S$ of beams. $$\begin{array}{|c|c|c|c|c|} (1,1,*) & (3,3,*)& (5,5,*) &\hdots & (2019,2019,*) \\[4pt] (*,2,1) & (*,4,2) & (*,6,5) & \hdots & (*,2020,2019) \\[4pt] (2,*,2) & (4,*,4) & (6,*,6) & \hdots & (2020,*,2020) \end{array}$$It's easy to see that this works. In particular, it suffices to verify that if $(x,y,*)\in S$, then there are two beams with $x$-coordinate $x\pm 1$ and two beams with $y$-coordinate $y\pm 1$; and analogously for the other two directions. The verification is straightforward. Lower Bound: If there are no beams in a certain direction (assume that it's $z$), then it's easy to see that the entire cube must be filled. Hence at least $n^2$ beams are present. Otherwise, we imagine reading through the $x$-coordinate of each beam. Since at least one number (besides $*$) is present, by the problem's condition, we must have read $1,2,3,\hdots,n$ at least once. Similarly, we have read $1,2,3,\hdots,n$ in the list of $y$ or $z$-coordinates at least once. Hence at least $3n$ numbers must appear. As each beam contains at most two numbers, we get that at least $3n/2$ beams must be present.
22.06.2020 23:36
Replace $2020$ with an arbitrary even number $n=2k$. We claim that the answer is $1.5n$, so the answer is $\boxed{3030}$. Part 1: Lower Bound Impose an $xyz$-coordinate system onto the cube. Suppose that there exists a beam in any $xy$-plane. Then, by the problem condition, there must also be a beam in both neighboring $xy$-planes, etc. By analogous arguments, if there exists a beam in every direction, then there is a beam in every $xy$-, $yz$-, and $zx$- plane, so supposedly we would need $3n$ beams, but since each beam can fulfill two of these planes, we only need $1.5n$ beams. The ceiling function comes from the fact that there must be an integral number of beams; it doesn't matter for evens. Note that if there is no beam in say, any $xy$-plane, then there must only be $z$-oriented beams, so $n^2$ beams would be required, clearly non-optimal. Part 2: Construction We construct by recursing from $n=2k$ to $n=2k+2$. Here's the $n=2$ construction: [asy][asy] import three; currentprojection=orthographic(1,-1/3,0.45); size(150); draw((0,0,0)--(8,0,0)); draw((0,0,0)--(0,8,0)); draw((0,0,0)--(0,0,8)); path3[] big = box((0,0,0), (8,8,8)); draw(big, dashed); draw(surface((8,4,4)--(8,8,4)--(8,8,0)--(8,4,0)--cycle, new pen[] {red,red,red,red}),nolight); draw(surface((8,4,0)--(0,4,0)--(0,4,4)--(8,4,0)--cycle, new pen[] {white,white,white,white}), nolight); draw(surface((8,8,4)--(0,8,4)--(0,4,4)--(8,4,4)--cycle, new pen[] {white,white,white,white}), nolight); path3[] xbeam = box((8,4,0),(0,8,4)); draw(xbeam, red); draw(surface((0,0,8)--(4,0,8)--(4,4,8)--(0,4,8)--cycle, new pen[] {red,red,red,red}),nolight); draw(surface((0,0,8)--(4,0,8)--(4,0,0)--(0,0,0)--cycle, new pen[] {white,white,white,white}), nolight); draw(surface((4,0,8)--(4,4,8)--(4,4,0)--(4,0,0)--cycle, new pen[] {white,white,white,white}), nolight); path3[] zbeam = box((0,0,8),(4,4,0)); draw(zbeam, red); draw(surface((4,0,4)--(4,0,8)--(8,0,8)--(8,0,4)--cycle, new pen[] {red,red,red,red}),nolight); draw(surface((4,0,8)--(8,0,8)--(8,8,8)--(4,8,8)--cycle, new pen[] {white,white,white,white}), nolight); draw(surface((8,0,4)--(8,0,8)--(8,8,8)--(8,8,4)--cycle, new pen[] {white,white,white,white}), nolight); path3[] ybeam = box((4,0,4), (8,8,8)); draw(ybeam, red); draw(big, dashed); draw((0,0,0)--(8,0,0)); draw((0,0,0)--(0,8,0)); draw((0,0,0)--(0,0,8)); [/asy][/asy] Now we recurse to an $(n+2)\times (n+2)\times (n+2)$ cube by placing the construction for $n\times n\times n$ into the corner, extend all the beams, then add the three red beams, as shown (Note that the three red beams are just the $2\times 2\times 2$ construction, but extended. Therefore, this construction can be reworded as just repeating $2\times 2\times 2$ many times). By the inductive hypothesis, all beams in the $n\times n\times n$ are satisfied, except for the two blue beams shown (after adding the red beams, when we want to go from $n+2$ to $n+4$, note that the two beams affected will still be analogous to the two blue beams shown). Indeed, these are the only two beams with sides that will no longer touch a face of a cube. [asy][asy] import three; currentprojection=orthographic(1,-1/3,0.55); size(250); draw((0,0,0)--(8,0,0)); draw((0,0,0)--(0,8,0)); draw((0,0,0)--(0,0,8)); path3[] big = box((0,0,0), (8,8,8)); draw(big, dashed); path3[] small = box((0,0,0),(6,6,6)); draw(small, dashed); path3[] tiny = box((6,6,6),(8,8,8)); draw(tiny, dashed); draw(surface((6,5,5)--(6,6,5)--(6,6,4)--(6,5,4)--cycle, new pen[] {blue,blue,blue,blue}),nolight); draw(surface((6,5,4)--(0,5,4)--(0,5,5)--(6,5,5)--cycle, new pen[] {white,white,white,white}), nolight); draw(surface((6,6,5)--(0,6,5)--(0,5,5)--(6,5,5)--cycle, new pen[] {white,white,white,white}), nolight); path3[] oldxbeam = box((6,5,4),(0,6,5)); draw(oldxbeam, blue); draw(surface((5,0,5)--(5,0,6)--(6,0,6)--(6,0,5)--cycle, new pen[] {blue,blue,blue,blue}),nolight); draw(surface((5,0,6)--(6,0,6)--(6,6,6)--(5,6,6)--cycle, new pen[] {white,white,white,white}), nolight); draw(surface((6,0,5)--(6,0,6)--(6,6,6)--(6,6,5)--cycle, new pen[] {white,white,white,white}), nolight); path3[] oldybeam = box((5,0,5), (6,6,6)); draw(oldybeam, blue); draw(surface((8,7,7)--(8,8,7)--(8,8,6)--(8,7,6)--cycle, new pen[] {red,red,red,red}),nolight); draw(surface((8,7,6)--(0,7,6)--(0,7,7)--(8,7,7)--cycle, new pen[] {white,white,white,white}), nolight); draw(surface((8,8,7)--(0,8,7)--(0,7,7)--(8,7,7)--cycle, new pen[] {white,white,white,white}), nolight); path3[] xbeam = box((8,7,6),(0,8,7)); draw(xbeam, red); draw(surface((6,6,8)--(7,6,8)--(7,7,8)--(6,7,8)--cycle, new pen[] {red,red,red,red}),nolight); draw(surface((6,6,8)--(7,6,8)--(7,6,0)--(6,6,0)--cycle, new pen[] {white,white,white,white}), nolight); draw(surface((7,6,8)--(7,7,8)--(7,7,0)--(7,6,0)--cycle, new pen[] {white,white,white,white}), nolight); path3[] zbeam = box((6,6,8),(7,7,0)); draw(zbeam, red); draw(surface((7,0,7)--(7,0,8)--(8,0,8)--(8,0,7)--cycle, new pen[] {red,red,red,red}),nolight); draw(surface((7,0,8)--(8,0,8)--(8,8,8)--(7,8,8)--cycle, new pen[] {white,white,white,white}), nolight); draw(surface((8,0,7)--(8,0,8)--(8,8,8)--(8,8,7)--cycle, new pen[] {white,white,white,white}), nolight); path3[] ybeam = box((7,0,7), (8,8,8)); draw(ybeam, red); label("$n$", (1.5,0,-1)); label("$2$", (5.5,0,-1)); [/asy][/asy] It is easy to check three conditions now: The three total affected sides of the two blue beams, after extension, are covered by our three new red beams. All faces of our three red beams are satisfied. The red beams do not collide with any extended beams from the $n\times n\times n$ cube. As we add $3$ beams every time $n$ increases by $2$, this gives a valid construction for $3k$ beams in a $(2k)\times(2k)\times (2k)$ cube, as desired. Combining both parts, the lower bound and the construction, shows that $3030$ is indeed optimal.
23.06.2020 07:02
Here is another interesting way for proving minimality on evens. My visualizing is bad so I can't tell if its a fakesolve Let $n=2k$. The base case $k=1$ is trivial. We proceed by induction. We split the cube into two parts. Consider a $2(n-1)\cdot 2(n-1)\cdot 2(n-1)$ part in the corner. If a beam crosses it, it's "old". By inductive hypothesis, we need at least $3(n-1)$ beams to cover the old part so that we don't need to insert anything new. We now extend each beam from length $2(n-1)$ to $2n$. We actually need to consider a few cases before blindly using induction. First of all, extra beams will need to be added because there must be some beams on the outskirts of the 2(n-1) cube, as that entire cube is covered. Then ugly casework should suffice. C1: Two beams for outskirts (Trivial) C2: One beam to cover outskirts: then we can label the xyz: the original cube has $x,y,z \in \{1,2,\cdots, 2n-2\} $. Say we're covering $x=y=2n-2$. Then we can cover with $x=z=2n-1$ and then we need one to cover $x=z=2n-1$, which can give us $y=z=2n$ but we need to cover $y=z=2n$ with $x=2n, y=2n-1$ Similar cases can be dealt this way.
17.08.2020 12:32
I claim that the answer is $\boxed{3030}$. But I'm only going to show the construction because I am a lazy person (And I'm late for posting this). But to prove the lower bound, you can just consider $1 \times 2020 \times 2020$ rectangular prisms and place them in the cube with a simple argument. Construction:
Attachments:

17.08.2020 17:14
My messy solution can be found here. Pretty sure it's a solve, although my phrasing was kinda bad. (I can share my solutions now online because scores are already out )
21.08.2020 07:04
The answer is $\boxed{3030.}$ We define an $x$-beam to be a beam whose long sides are parallel to the $x$-axis, and define $y$-beams and $z$-beams similarly. Construction: Orient the cube in the $xyz$-plane such that its faces are parallel to the coordinate axes. For each unit cube, we describe it with coordinates $(x,y,z)$ for positive integers $x,y,z$, such that the bottom-left corner of the cube has coordinates $(1,1,1)$ and the top-right corner of the cube has coordinates $(2020,2020,2020)$. Now, remark that a beam can be characterized by $2$ of the $3$ coordinates; for example, $(1,1,-)$ is the $z$-beam passing through the cube $(1,1,1)$. Now, for each $1 \leq i \leq 1010$, consider the beams $$(2i-1,2i-1,-) \hspace{1cm} (2i,-,2i-1) \hspace{1cm} (-,2i,2i-1)$$One can easily check that these $3030$ beams satisfy the problem condition, as desired. Lower Bound: Let $a,b,c$ be the number of $x$-beams, $y$-beams, and $z$-beams, respectively. Remark that there must be at least $1$ $y$-beam or $z$-beam in each $1 \cdot y \cdot z$ plane, otherwise the third condition wouldn't be satisfied. Thus since there are $2020$ such planes, we find that $b+c \geq 2020$. Similarly, we find that $a+b \geq 2020$ and $a+c \geq 2020$, thus $a+b+c \geq 3030$ as desired.
21.08.2020 22:58
AOPS12142015 wrote: 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? Proposed by Alex Zhai I hope this is right... The answer is $\boxed{3030}$. Use the same construction as everyone else. Proof of minimality. [asy][asy] import three; currentprojection=orthographic(2, -3, 2.5); size(150); draw((0,0,0)--(8,0,0)--(8,8,0)--(0,8,0)--cycle,red); draw((0,8,0)--(0,8,8),red); draw(scale(1,8,1)*shift(6,0,0)*unitcube, mediumgreen); draw(scale(1,8,1)*shift(6,0,1)*unitcube, palegreen); draw(scale(8,1,1)*shift(0,6,2)*unitcube,lightred); draw(scale(1,8,1)*shift(4,0,3)*unitcube, mediumgreen); draw(scale(8,1,1)*shift(0,1,4)*unitcube,lightred); draw(scale(8,1,1)*shift(0,1,5)*unitcube,red); draw(scale(8,1,1)*shift(0,1,6)*unitcube,lightred); draw(scale(1,8,1)*shift(1,0,7)*unitcube, mediumgreen); //draw(scale(1,1,8)*shift(7,6,0)*unitcube,lightgray); draw((0,0,0)--(0,0,8),red); draw((8,8,0)--(8,8,8),red); draw((8,0,0)--(8,0,8),red); draw((0,0,8)--(8,0,8)--(8,8,8)--(0,8,8)--cycle,red); [/asy][/asy] There are $3$ directions of beams: vertical (blue), green, and red. Suppose that we use under three types of beams. If we only use one, then to leave no face exposed, we need to fill up the entire cube. This requires $2020^2$ of them. If we only use two, then WLOG they be "red" and "green". Separate the cube into $2020$ horizontal layers; clearly each red or green beam is contained entirely inside exactly one layer. In each layer, we clearly cannot have both a red beam and a green beam; they necessarily intersect. So in each layer there is at most one kind of beam, and we need $2020$ beams in each non-empty layer to prevent the beam from moving horizontally. I claim that each layer must have at least one beam. Suppose otherwise, i.e. there exists a layer with no beam. Since there is a beam, WLOG there is a beam in a layer above the empty one with no beam in the layer below it. But then it has its bottom face exposed, contradiction. Since there is a beam in every layer, there are $2020$ beams in every layer, and we still need $2020^2$ beams. Consider when we have beams in all three directions. Take any beam $b_1$ completely contained in the bottom layer. One must exist; note that vertical beams do not affect the top or bottom faces of any horizontal beam -- now use the same argument above. There must be a beam $b_2$ touching its top face, a beam $b_3$ touching $b_2$'s top face, etc. So we need $2020$ beams each completely contained in a "$xy$" horizontal layer. Similarly, we need $2020$ beams in each contained in each $xz$ layer, and $2020$ beams in each $yz$ layer. Each beam is in exactly two layers (for example, a beam in the $z$ vertical direction is in exactly one $xz$ layer and one $yz$ layer). So we need at least $\frac{2020\cdot 3}{2}=3030$ beams.
01.09.2020 01:35
We claim the answer is $3030$ beams. For the remainder of this proof we will refer to the condition that long beam faces must touch another face as the "gravity condition". We will first prove the bound. Evidently if all the beams are oriented the same way then we get $2020^2$. Assume that the beams are not all oriented the same way. We focus on $xy$-plane beams first: Let $N_x$ and $N_y$ be the number of each type. If there are less than $2020$ x and y beams in total, then by Pigeonhole there must be some z-layer that has no xy-beams through it. This is evidently not okay. Hence we need $N_x + N_y \geq 2020$. We can get similar bounds for $y, z$ and $x, z$. Summing the inequalities up and dividing, we find $N_x + N_y + N_z \geq 3030$. For a construction, we can place down $1010$ of each beam. We refer to a coordinate system for our construction(because I don't know how to draw a nice picture w/ latex/asy ), where $(1, 1, 1)$ represents the first unit square, and not points. z-beams: $(1, 1, z), (3, 3, z), \cdots (2019, 2019, z)$. y-beams: $(2, y, 1), (4, y, 1), \cdots (2020, y, 2019)$. x-beams: $(x, 2, 2), (x, 4, 4), \cdots, (x, 2020, 2020)$.
24.02.2021 03:37
A rushed and poorly-worded writeup... The answer is $3030$. The construction is the same as everyone else's, with the diagonals spaced apart. I'm bad at asymptote though so I can't make one myself. Denote the set of all beams facing in the $x,y,z$ directions (that is which way the long ends point) as $B_x,B_y,B_z$ respectively. We will prove the following claims: Claim 1: If any of $B_x,B_y,B_z$ are empty we do not get an optimal construction. Proof: WLOG let $B_x=0$. Then we see that every single unit cube in the bigger cube must be filled, which means we need to use $2n^2>3n$ beams. Claim 2: If none of $B_x,B_y,B_z$ are empty then there must be a beam which touches each face of the cube at a $1\times n$ face. Proof: We will show that there exists a beam touching both of the $x$-direction faces. The other cases are similar. Since none of $B_y,B_z$ are empty there must be a $y$-facing beam. Then there must be a $y$ or $z$ facing beam above it (here we take $x$ to be the up-down axis), and another above that, and so on until we reach the top face. The bottom face is similar. Now we will prove that this is a lower bound using induction. Replace $2020\times 2020 \times 2020$ with $2n \times 2n \times 2n$. We claim the answer here is $3n$. For $n=1,2$ this is obviously true. Now suppose we have an $n \times n \times n$ cube. Split it into an $(n-1) \times (n-1) \times (n-1)$ cube that resides in the top-left rear corner and the rest of the cube. Call a beam old if a part of it is contained within this smaller cube, and new otherwise. By inductive hypothesis the minimum number of beams that can cover this smaller cube is $3(n-1)$. Now consider the state of the beams if we pretended the new ones didn't exist and only considered the old ones. If one of $B_x,B_y,B_z$ were zero, then we would need at least $2(n-1)^2$ old beams alone, which is more than $3n$. Therefore this case doesn't mess up our minimum. Otherwise, if none of the $B_x,B_y,B_z$ were zero, then the three faces of the smaller cube that were not contained within the faces of the new cube must have a $1 \times n$ beam touching them. To account for this, when we look at the new beams, at least one of them must be touching each of these "previous faces" from the "outside" of the smaller cube. Since it's obvious that a beam can't touch two faces at the same time this way, this means that we need at least $3$ new beams. Combining this with our inductive hypothesis, we get that we require at least $3n$ beams to fill an $n \times n \times n$ cube. Then plugging in $n=1010$ finishes.
23.08.2021 17:24
We solve for all even $n$ the problem of filling an $n\times n\times n$ cubes. We first claim there are at least $\frac32 n$ beams. Label beams by their direction: $x,y,z$. If there's only one direction, there must be $n^2\geq \frac32 n$. Otherwise, we double count the "slabs", which are sets of $n^2$ unit cubes with the same $x,y,z$ value. Note that it is clear by induction that each slab must have at least one beam completely contained in it. Thus, \[3n = \text{num. of slabs} \leq 2 \cdot \text{number of beams}\]Since each beam is completely contained by 2 slabs. Thus, the number of beams is at least $\frac32 n$. As for the construction, the $n=2$ construction (disjoint $x,y,z$ beams) can be placed with constant orientation into the $2\times 2\times 2$ cubes along a diagonal, and then the beams extended to the edges. This clearly satisfies the conditions and we're done. $\blacksquare$.
25.08.2021 18:28
11.02.2022 07:06
We claim the answer is $3030$. Define a slab to be a $2021 \times 2021 \times 1$ prism. First, assume that two beams share an entire face, it is clear to see that such a construction would need $>3030$. Now, assume no such pair of beams exist. Claim: All slabs contain a beam Consider an arbitrary beam $A$ which shares a side with $B$. Notice that $A$ and $B$ are perpendicular and thus there is a slab of each orientation that completely contains a beam. Assume a slab $S_1$ contains a beam and let $S_2$ be a slab that shares a face with $S_1$. Notice that $S_2$ must also contain a beam by the third condition. Thus, proceeding inductively, each slab with the same orientation of $S_1$ contains a beam. But, since there is a least one slab per orientation, every slab contains a beam. $\square$ Notice that a beam is the intersection of two perpendicular slabs since each slab contains a beam, this implies there must be at least $\frac{2020 \cdot 3}{2}=3030$ beams. For the construction, my diagram was super sloppy so refer to the ones from the previous posts. $\blacksquare$
16.01.2023 02:28
We claim that the answer is 3030. To achieve 3030, put a high beam along every other stack along the main diagonal (1010), and do a similar thing with respect to each axis. An example of this for a 4x4x4 cube: 1st Layer:$(1,0,0,0;3,3,3,3;0,0,2,0;0,0,0,0)$ 2nd Layer: $(1,5,0,0;0,5,0,0;0,5,2,0;0,5,0,0)$ 3rd Layer: $(1,0,0,0;0,0,0,0;0,0,2,0;4,4,4,4)$ 4th Layer: $(1,0,0,6;0,0,0,6;0,0,2,6;0,0,0,6)$ where each nonzero number corresponds to a certain beam and 0 corresponds to no beam. If there is a layer that contains no beams entirely within that layer, then the only way to fill the layer is to use $2020^2$ beams perpendicular to it, but we disregard this since we know that this is not optimal. Otherwise, each layer contains at least one beam within it. This means that there are a total of at least 2020 beams that are either horizontal or vertical. Similarly, there are at least 2020 beams that are either horizontal or high, and at least 2020 beams that are either vertical or high. Therefore, there are at least 3030 beams, so we are done.
07.09.2023 02:48
Pretty easy problem to build intuition, after getting that the problem generalizes readily. Note that either there are 3 types of beams (we classify them as x,y,z beams) or 1 type; 1 type it's easy to see you'll fill up the entire box, not optimal; note also that it's unoptimal for a cross section to not fully contain a beam, since that needs 2020^2 beams, which we know we can try to get better. Now, suppose WLOG we look at x-y cross sections: There's at least 2020 beams that are x or y oriented, and analogously y-z and z-x have similar results, so adding them, we get $x+y+y+z+z+x\ge 6060$ implies there are at least 3030 beams. For the construction, I trust a different post has it but it's pretty hard to explain, though this part is easy to make based on smaller cases.
04.11.2023 23:42
The answer is $3030$, and the construction involves working our way diagonally upwards. First, align the cube in the 3D plane, and let there be $x$ beams all facing the $x$ direction, $y$ beams facing the $y$ direction, and $z$ beams facing the $z$ direction. Note that if one of $x$, $y$, $z$ is zero, then we would have to fill up the cube. (This is because for a square cross section, we would have to tesselate beams across it to satisfy the problem condition). Thus, assume that $x$, $y$, $z$ are all positive. Then the key claim is that \[ x + y \geq 2020 \]and the cyclic statements. The proof is by looking at a face of the cube perpendicular to an $x$ beam. For the problem condition to be satisfied, there must be one $x$ beam or one $y$ beam in each one of the rows of the face for the beams to be touching in the $y$-direction, implying that $x + y \geq 2020$. $\square$ Thus, we extract the inequality that $x + y + z \geq 3030$. $\blacksquare$
23.11.2023 22:15
Replace $2020$ with any even $n$. The answer is $3n/2$. Impose a coordinate system onto the configuration, where beams are of the form $(-, y, z)$, $(x, -, z)$, or $(-, y, z)$, depending on the faces they touch, and let $(0, 0, -)$ and its cyclic shifts correspond to the faces of a corner cube. Characterization of conditions. We first note that beams having intersecting interiors means that they share a common coordinate, which we prohibit. The face condition means that if all coordinates of a beam $B=(x, y, -)$ are between $1$ and $n-2$, inclusive, there exist beams with an $x$-coordinate of $x \pm 1$ and beams with an $y$-coordinate of $y \pm 1$. (This analogously holds for beams that protrude from other face pairs.) Construction. We use the construction \[ (0, 0, -), (2, 2, -), (4, 4, -), \dots, (2018, 2018, -) \]\[ (1, -, 0), (3, -, 2), (5, -, 4), \dots, (2019, -, 2018) \]\[ (-, 1, 1), (-, 3, 3), (-, 5, 5), \dots, (-, 2019, 2019) \] Lower bound. First, note that if no beams protrude from some face, then we require all $n$ slabs adjacent to that face to be filled, which requires at least $n^2$ beams. Assume henceforth that each face has at least one beam that protrudes from it. Let $e(x)$ be the number of $x$-beams, and similarly define $e(y)$ and $e(z)$. Claim: Every slab of the cube contains the entirety of at least one beam. Proof. Consider a slab $\mathcal{S}$ (WLOG aligned with the $z$-axis) that contains a complete beam, which exists per our assumption. It follows that any slab $\mathcal{S}'$ that shares a face with $\mathcal{S}$ contains a complete beam, so by induction all $xy$-slabs must contain at least one beam. Thus, each number $0, 1, \dots, n-1$ appears at least once among the $x$ and $y$-beams, so \[ e(x)+e(y) \ge n. \]Analogously, \[ e(x)+e(z) \ge n \]and \[ e(y)+e(z) \ge n, \]so summing the three inequalities and dividing by $2$ returns \[ e(x) + e(y) + e(z) \ge 3n/2, \]as claimed.
05.01.2024 08:00
Place the cube in the $xyz$-plane with one corner at the origin in the positive octant. Note that there are three types of beams, $X, Y, Z$ referring to the axis they are parallel to. We claim that the minimum number of beams to satisfy the conditions is $3030.$ Consider if a certain type of beam was not present in a configuration. WLOG the $Z$ bars. If we split the cube into layers parallel to the $xy$-plane, we notice no beam crosses between layers. Furthermore, if there is an $X$ bar in one layer, there cannot be a $Y$ bar. To satisfy the tangency conditions in the problem, the $X$ bar must have adjacent bars in the layer and we observe the entire layer is completed with $2020$ bars. Therefore the entire configuration has $2020^2$ bars. Henceforth assume that every type of bar occurs in the setup. Now consider the three splittings of the cube, layering by parallel to $xy, xz, yx$-planes similar to before. FTSOC let their exist layers without a beam completely in it (e.g. in the $xy$-plane parallel layering, there is a layer without $X, Y$ beams). Since all types of beams exist, there is a layer with a beam completely in it. So there must be two consecutive layers, one with a beam completely in it and another without. This contradicts the tangency condition though as the face of the beam will not touch any beam in the adjacent layer. Therefore, there is at least one beam in all $3\cdot 2020$ layers. Since each beam lies in two orthogonal layers, there are at least $\frac{3}{2} \cdot 2020 = 3030$ beams. Now we prove a construction for the minimality. Denote a beam $(a, b, c)$ where $a$ denotes the type of beam, and the pair $(b,c)$ represents the grid coordinate of the square faces of the beam on the corresponding plane (e.g a $Z$ bar in the corner of the cube with origin as a vertex is $(Z, 1, 1)$). Consider beams, \begin{align*} &(Z, 1, 1), (Z, 3, 3), \dots, (Z, 2019, 2019), \\ &(X, 2, 1), (X, 4, 3), \dots, (X, 2020, 2019), \\ &(Y, 2, 2), (Y, 4, 4), \dots, (Y, 2020, 2020). \\ \end{align*}For a bar $(Z, i, i)$, note that there is $(X, i-1, i-2)$ (or wall) and $(X, i+1, i)$ bordering two internal sides. Also there are $(Y, i-1, i-1), (Y, i+1, i+1)$ tangent to the other sides. We can use a similar logic to prove the other beams, trust.
23.02.2024 00:29
10.08.2024 23:58
Let the cube and beams have axis parallel to $x, y, z$-axis. If we can use no more than two types of beams (WLOG $x, y$-axis), consider the situation after we complete a legal placement of beams. Since $x$-beams and $y$-beams cannot lie on the same $z$ level, if a beam exists on a particular $z$ level, then that type of beam must fill the entire $xy$ plane on that $z$ level. Furthermore since the top and bottom of each filled $xy$ plane must be touching something, all the $z$-levels must be filled. This requires $n^2$ beams. If we must use exactly $3$ types of beams: Since every $xy$ plane in the cube must contain either a $x$-beam or $y$-beam, $$N_x + N_y \ge n.$$Similarly, $$N_y+N_z \ge n$$and $$N_z+N_z \ge n.$$Adding these together and dividing by $2$ gives $$N_x+N_y+N_z \ge \frac{3n}{2}.$$A construction that uses $\frac{3n}{2}$ beams is the following: place a $x$, and then $y$, and then $z$ beam repeatedly for $\frac{n}{2}$ times, while making sure each beam placement is the 'lowest it can go' ($x$ beams go to lowest possible $yz$ coordinate, $y$ beams go to lowest possible $xz$ coordinate, and $z$ beams go to lowest possible $xy$ coordinate). Thus, the answer is $\boxed{3030}.$
09.10.2024 06:37
For a general even $n$, I claim the answer is $\boxed{\frac{3n}{2}}$. Define an $x$-oriented, $y$-oriented, and $z$-oriented type beam to be one with their $1 \times 1$ base parallel to the respective axis. Bound: If all the beams are of the same type, we obviously obtain the bound of $n^2$. This is not optimal so we can safely disregard. Therefore, there must be at least one beam of each type. For each "slab" of the cube, I claim that there must be one beam fully inside that slab. Consider an $xy$-parallel slab for now. Because there is one beam of each type, only look at $x$-oriented and $y$-oriented beams. Because of their top bottom faces, they must work themselves up and down the cube wrt to the $z$-axis. A $z$-oriented beam cannot be touching the top or bottom face of a $x$ or $y$ oriented beam, simply because it cannot fit, so our claim is true. Now from this claim, we know there are at least $n$ beams that are $x$ or $y$ oriented, or for any pair of orientations for that matter. Double count each beam to obtain the lower bound as shown. Construction: If you want you can look at rd123's asy which desmonstrates it well. For the sake of write up, I will also explain it here. Take an isometric view of the cube, and take the vertex as the "origin". Label $x$ to the left and $y$ to the right. In the $xy$ plane, fill in the beams with $1 \times 1$ face at $(-n+2k, 2k+1, 0)$ for all nonnegative integers $k$ within the cube. For the $yz$ plane, take $(0, 2k, -2k)$ for all positive integers $k$ within the cube. For the $xz$ plane, take $(-2k-1, 0, -n+2k+1)$ for all nonegative integers $k$ within the cube. This obviously works, and I don't feel like elaborating furhter because I need to sleep.