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 USAMO Problems/Problem 2"

m (→‎Problem: bulleted list)
(→‎Solution)
 
(2 intermediate revisions by 2 users not shown)
Line 9: Line 9:
  
 
== Solution ==
 
== Solution ==
−
{{Solution}}
+
Take one vertex of the cube as origin and establish 3D coordinates along the cube's edges.
  
−
{{USAMO box|year=2020|num-b=1|num-a=3}}
+
Define a beam as <math>x-dir</math> if its long edge is parallel to x-axis. Similarly for <math>y-dir</math> and <math>z-dir</math>.
 +
 
 +
Define a beam's location as (direction, (<math>1 \times 1</math> face's location in 2D coordinate).
 +
 
 +
For example, (y, 2, 4) indicates the beam with vertex (1, 0, 3) and (2, 2020, 4)
 +
 
 +
Apparently <math>x</math> beam needs the other <math>x</math> or <math>y</math> beams to touch its <math>xy</math> faces, <math>x</math> or <math>z</math> beams to touch its <math>xz</math> faces. Similarly for <math>y</math> and <math>z</math> beam.
 +
 
 +
If there are only 1-dir or 2-dirs beams, it is easy to approve that <math>2020 \times 2020</math> is the minimal number beams.
 +
 
 +
(for example, if only use <math>x-dir</math> and <math>y-dir</math> beams, all the <math>x-dir</math> beams's xz faces can only be touched by <math>x-dir</math> beams. In the other word, <math>2020 x-dir</math> beams will be stacked to meet xz faces touch requirements in that xz layer)
 +
 
 +
Consider cases with all <math>3-dirs</math> beams.
 +
WLOG there is a <math>x-dir</math> beam and it needs <math>x-dir</math> or <math>y-dir</math> beams to touch its <math>xy</math> faces (unless it touches the cube surface).
 +
 
 +
And this <math>y-dir</math> beam also needs a <math>x-dir</math> or <math>y-dir</math> to touch it's <math>xy</math> faces. And so on until one which touches cube surface. So from <math>xy</math> face perspective, it needs <math>2020</math> beams.
 +
 
 +
Similarly from <math>xz</math> and <math>yz</math> face perspective, it also needs <math>2020</math> and <math>2020</math> beams.
 +
 
 +
Consider one beam has four <math>1 \times 2020</math> faces and it can be counted twice. So there should be at least <math>2020 \times 3 \div 2=3030</math> beams.
 +
 
 +
Here is one solution with 3030 beams.
 +
 
 +
<math>(x, 1, 1),\ (y, 1, 2),\ (z, 2, 2),</math>
 +
 
 +
<math>\cdots , </math>
 +
 
 +
<math>(x, (2n+1), (2n+1)),\ (y, (2n+1), (2n+2)),\ (z, (2n+2), (2n+2)),</math>
 +
 
 +
<math>\cdots , </math>
 +
 
 +
<math>(x, (2019, 2019)),\ (y, 2019, 2020),\ (z, 2020, 2020)</math>
 +
 
 +
{{USAMO newbox|year=2020|num-b=1|num-a=3}}
  
 
{{MAA Notice}}
 
{{MAA Notice}}

Latest revision as of 04:39, 23 December 2023

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 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?

Solution

Take one vertex of the cube as origin and establish 3D coordinates along the cube's edges.

Define a beam as $x-dir$ if its long edge is parallel to x-axis. Similarly for $y-dir$ and $z-dir$.

Define a beam's location as (direction, ($1 \times 1$ face's location in 2D coordinate).

For example, (y, 2, 4) indicates the beam with vertex (1, 0, 3) and (2, 2020, 4)

Apparently $x$ beam needs the other $x$ or $y$ beams to touch its $xy$ faces, $x$ or $z$ beams to touch its $xz$ faces. Similarly for $y$ and $z$ beam.

If there are only 1-dir or 2-dirs beams, it is easy to approve that $2020 \times 2020$ is the minimal number beams.

(for example, if only use $x-dir$ and $y-dir$ beams, all the $x-dir$ beams's xz faces can only be touched by $x-dir$ beams. In the other word, $2020 x-dir$ beams will be stacked to meet xz faces touch requirements in that xz layer)

Consider cases with all $3-dirs$ beams. WLOG there is a $x-dir$ beam and it needs $x-dir$ or $y-dir$ beams to touch its $xy$ faces (unless it touches the cube surface).

And this $y-dir$ beam also needs a $x-dir$ or $y-dir$ to touch it's $xy$ faces. And so on until one which touches cube surface. So from $xy$ face perspective, it needs $2020$ beams.

Similarly from $xz$ and $yz$ face perspective, it also needs $2020$ and $2020$ beams.

Consider one beam has four $1 \times 2020$ faces and it can be counted twice. So there should be at least $2020 \times 3 \div 2=3030$ beams.

Here is one solution with 3030 beams.

$(x, 1, 1),\ (y, 1, 2),\ (z, 2, 2),$

$\cdots ,$

$(x, (2n+1), (2n+1)),\ (y, (2n+1), (2n+2)),\ (z, (2n+2), (2n+2)),$

$\cdots ,$

$(x, (2019, 2019)),\ (y, 2019, 2020),\ (z, 2020, 2020)$

2020 USAMO (Problems • Resources)
Preceded by
Problem 1 		Followed by
Problem 3
1 • 2 • 3 • 4 • 5 • 6
All USAMO Problems and Solutions

The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions. AMC logo.png

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2020_USAMO_Problems/Problem_2&oldid=208201"