Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "2020 USOJMO Problems/Problem 3"

(→‎Problem)
(→‎Solution)
Line 20: Line 20:
 
We can repeat this process 1010 times, placing the beams in groups of 3 so that beam <math>3n+1</math> is 2 units up and right of beam <math>3n-2</math>, beam <math>3n+2</math> is 2 units forward and up of beam <math>3n-1</math>, and beam <math>3n+3</math> is 2 units forward and right of beam <math>3n</math>, for all <math>1\leq n \leq 1009</math>. 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).
 
We can repeat this process 1010 times, placing the beams in groups of 3 so that beam <math>3n+1</math> is 2 units up and right of beam <math>3n-2</math>, beam <math>3n+2</math> is 2 units forward and up of beam <math>3n-1</math>, and beam <math>3n+3</math> is 2 units forward and right of beam <math>3n</math>, for all <math>1\leq n \leq 1009</math>. 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 <math>A</math> x-oriented beams, <math>B</math> y-oriented beams, and <math>C</math> z-oriented beams. Now look each <math>2020 \times 1 \times 2020</math> slice of the cube, parallel to the xz-plane. Note there are 2020 such slices. There are two cases. Either <math>B=2020^2</math>, or at least one of A or C is nonzero. In the first case, we clearly have at least <math>2020^2>3030</math> beams as desired. In the second case, we must have at least one beam in each <math>2020 \times 1 \times 2020</math> 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 <math>2020 \times 1 \times 2020</math> slice, so <math>A+C\geq 2020</math>. Similarly, we must have <math>A=2020^2</math>, <math>C=2020^2</math>, or both <math>A+B\geq 2020</math> and <math>B+C\geq 2020</math>. In every case, the number of beams, <math>A+B+C</math>, will be at least 3030 as desired.
+
Thus, we have shown that 3030 beams suffices, so we will now show that 3030 beams is the minimum. Let there be <math>A</math> x-oriented beams, <math>B</math> y-oriented beams, and <math>C</math> z-oriented beams. Now look each <math>2020 \times 1 \times 2020</math> slice of the cube, parallel to the xz-plane. Note there are 2020 such slices. There are two cases. Either <math>B=2020^2</math>, or at least one of A or C is nonzero. In the first case, we clearly have at least <math>2020^2>3030</math> beams as desired. In the second case, we must have at least one beam in each <math>2020 \times 1 \times 2020</math> 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 <math>2020 \times 1 \times 2020</math> slice, so <math>A+C\geq 2020</math>. Similarly, we must have <math>A=2020^2</math>, <math>C=2020^2</math>, or both <math>A+B\geq 2020</math> and <math>B+C\geq 2020</math>. In every case, the number of beams, <math>A+B+C</math>, will be at least 3030 as desired.<math>\blacksquare</math>

Revision as of 12:06, 7 July 2020

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 [i]beam[/i] 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?

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 $(x, y, z)$ if it is centered at $(x, y, z)$. Place the $2020 \times 2020 \times 2020$ cube so that the edges are parallel to the axes, and two of its corners are at $(1, 1, 1)$ and $(2020, 2020, 2020)$. 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.

I claim that the answer is $\boxed{3030}$. First we will prove 3030 suffices. Place the first beam so its endpoints lie at $(1, 1, 1)$, and $(2020, 1, 1)$. Place the 2nd beam so its endpoints lie at $(1, 1, 2)$ and $(1, 2020, 2)$. Place the 3rd beam so its endpoints lie at $(2, 2, 1)$ and $(2, 2, 2020)$. Now it is clear that the only faces among these three beams that are not touching the faces of the $2020 \times 2020 \times 2020$ 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 $(1, 3, 3)$ to $(2020, 3, 3)$, 2 units up and right of beam 1. Then place beam 5 from $(3, 1, 4)$ to $(3, 2020, 4)$, 2 units forward and up of beam 2. Place beam 6 from $(4, 4, 1)$ to $(4, 4, 2020)$, 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 $3n+1$ is 2 units up and right of beam $3n-2$, beam $3n+2$ is 2 units forward and up of beam $3n-1$, and beam $3n+3$ is 2 units forward and right of beam $3n$, for all $1\leq n \leq 1009$. 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 $A$ x-oriented beams, $B$ y-oriented beams, and $C$ z-oriented beams. Now look each $2020 \times 1 \times 2020$ slice of the cube, parallel to the xz-plane. Note there are 2020 such slices. There are two cases. Either $B=2020^2$, or at least one of A or C is nonzero. In the first case, we clearly have at least $2020^2>3030$ beams as desired. In the second case, we must have at least one beam in each $2020 \times 1 \times 2020$ 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 $2020 \times 1 \times 2020$ slice, so $A+C\geq 2020$. Similarly, we must have $A=2020^2$, $C=2020^2$, or both $A+B\geq 2020$ and $B+C\geq 2020$. In every case, the number of beams, $A+B+C$, will be at least 3030 as desired.$\blacksquare$

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2020_USOJMO_Problems/Problem_3&oldid=127673"