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 "2003 USAMO Problems/Problem 6"
 
Line 112: Line 112:
  
 
[[Category:Olympiad Combinatorics Problems]]
 
[[Category:Olympiad Combinatorics Problems]]
 +
{{MAA Notice}}

Latest revision as of 12:39, 4 July 2013

Problem

At the vertices of a regular hexagon are written six nonnegative integers whose sum is 2003. Bert is allowed to make moves of the following form: he may pick a vertex and replace the number written there by the absolute value of the difference between the numbers written at the two neighboring vertices. Prove that Bert can make a sequence of moves, after which the number 0 appears at all six vertices.

Solution

Assume the original numbers are $a,b,c,d,e,f$. Since $a+b+c+d+e+f$ is odd, either $a+c+e$ or $b+d+f$ must be odd. WLOG let $a+c+e$ be odd and $a\ge c\ge e \ge 0$.

Case 1

$a,c,e>0$. Define Operation A as the sequence of moves from Step 1 to Step 3, shown below:

[asy] size(300); defaultpen(fontsize(9)); label("$d$",expi(0),(0,0)); label("$c$",expi(pi/3),(0,0),red); label("$b$",expi(2*pi/3),(0,0)); label("$a$",expi(pi),(0,0),red); label("$f$",expi(4*pi/3),(0,0)); label("$e$",expi(5*pi/3),(0,0),red); label("Step 1",(0,-2),(0,0)); label("$c-e$",(5,0)+expi(0),(0,0)); label("$c$",(5,0)+expi(pi/3),(0,0),red); label("$a-c$",(5,0)+expi(2*pi/3),(0,0)); label("$a$",(5,0)+expi(pi),(0,0),red); label("$a-e$",(5,0)+expi(4*pi/3),(0,0)); label("$e$",(5,0)+expi(5*pi/3),(0,0),red); label("Step 2",(5,-2),(0,0)); label("$c-e$",(10,0)+expi(0),(0,0)); label("$c$",(10,0)+expi(pi/3),(0,0),red); label("$a-c$",(10,0)+expi(2*pi/3),(0,0)); label("$c-e$",(10,0)+expi(pi),(0,0),red); label("$a-e$",(10,0)+expi(4*pi/3),(0,0)); label("$a-c$",(10,0)+expi(5*pi/3),(0,0),red); label("Step 3",(10,-2),(0,0)); [/asy]

Notice that Operation A changes the numbers $a,c,e$ to $c-e,c,a-c$ and they are all nonnegative, since $a\ge c\ge e$. Their sum changes from $a+c+e$ to $a+c-e$; it decreases as long as $e\ne 0$. If we repeat Operation A enough times, its sum will decrease and eventually we will arrive at a point where at least one of the numbers in the positions originally occupied by $a,c,e$ has become a 0.

Case 2

$a,c>0$ and $e=0$. Define Operation B as the sequence of moves from Step 1 to Step 3, shown below:

[asy] size(300); defaultpen(fontsize(9)); label("$d$",expi(0),(0,0)); label("$c$",expi(pi/3),(0,0),red); label("$b$",expi(2*pi/3),(0,0)); label("$a$",expi(pi),(0,0),red); label("$f$",expi(4*pi/3),(0,0)); label("$0$",expi(5*pi/3),(0,0),red); label("Step 1",(0,-2),(0,0)); label("$c$",(5,0)+expi(0),(0,0)); label("$c$",(5,0)+expi(pi/3),(0,0),red); label("$a-c$",(5,0)+expi(2*pi/3),(0,0)); label("$a$",(5,0)+expi(pi),(0,0),red); label("$a$",(5,0)+expi(4*pi/3),(0,0)); label("$0$",(5,0)+expi(5*pi/3),(0,0),red); label("Step 2",(5,-2),(0,0)); label("$c$",(10,0)+expi(0),(0,0)); label("$\begin{array}{l}2c-a\\ a-2c\end{array}$",(10,0)+expi(pi/3),(0,0),red); label("$a-c$",(10,0)+expi(2*pi/3),(0,0)); label("$c$",(10,0)+expi(pi),(0,0),red); label("$a$",(10,0)+expi(4*pi/3),(0,0)); label("$0$",(10,0)+expi(5*pi/3),(0,0),red); label("Step 3",(10,-2),(0,0)); [/asy]

where in Step 3, we take the nonnegative choice of $2c-a$ or $a-2c$. $a,c,0$ is changed to either $c,2c-a,0$ or $c,a-2c,0$. If we have $c,2c-a,0$, their sum is $3c-a$ and this is less than $a+c+0$ (the original sum) unless $a=c$, but $a\ne c$ since the original sum $a+c+0$ is odd by assumption. If we have $c,a-2c,0$, their sum is $a-c$, which is less than $a+c$. Operation B applied repeatedly will cause either $a$ or $c$ to become $0$.

Case 3

$a>0$ and $c=e=0$. Define Operation C as the sequence of moves from Step 1 to Step 4, shown below:

[asy] size(400); defaultpen(fontsize(9)); label("$d$",expi(0),(0,0)); label("$0$",expi(pi/3),(0,0),red); label("$b$",expi(2*pi/3),(0,0)); label("$a$",expi(pi),(0,0),red); label("$f$",expi(4*pi/3),(0,0)); label("$0$",expi(5*pi/3),(0,0),red); label("Step 1",(0,-2),(0,0)); label("$0$",(5,0)+expi(0),(0,0)); label("$0$",(5,0)+expi(pi/3),(0,0),red); label("$a$",(5,0)+expi(2*pi/3),(0,0)); label("$a$",(5,0)+expi(pi),(0,0),red); label("$a$",(5,0)+expi(4*pi/3),(0,0)); label("$0$",(5,0)+expi(5*pi/3),(0,0),red); label("Step 2",(5,-2),(0,0)); label("$0$",(10,0)+expi(0),(0,0)); label("$0$",(10,0)+expi(pi/3),(0,0),red); label("$a$",(10,0)+expi(2*pi/3),(0,0)); label("$0$",(10,0)+expi(pi),(0,0),red); label("$a$",(10,0)+expi(4*pi/3),(0,0)); label("$0$",(10,0)+expi(5*pi/3),(0,0),red); label("Step 3",(10,-2),(0,0)); label("$0$",(15,0)+expi(0),(0,0)); label("$0$",(15,0)+expi(pi/3),(0,0),red); label("$0$",(15,0)+expi(2*pi/3),(0,0)); label("$0$",(15,0)+expi(pi),(0,0),red); label("$0$",(15,0)+expi(4*pi/3),(0,0)); label("$0$",(15,0)+expi(5*pi/3),(0,0),red); label("Step 4",(15,-2),(0,0)); [/asy]

See also

2003 USAMO (Problems • Resources)
Preceded by
Problem 5 		Followed by
Last question
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=2003_USAMO_Problems/Problem_6&oldid=54778"