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"

(New page: == 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 re...)
 
Line 4: Line 4:
  
 
== Solution ==
 
== Solution ==
−
{{solution}}
+
Assume the original numbers are <math>a,b,c,d,e,f</math>. Since <math>a+b+c+d+e+f</math> is odd, either <math>a+c+e</math> or <math>b+d+f</math> must be odd. WLOG let <math>a+c+e</math> be odd and <math>a\ge c\ge e \ge 0</math>.
  
 +
=== Case 1 ===
 +
<math>a,c,e>0</math>. 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 <math>a,c,e</math> to <math>c-e,c,a-c</math> and they are all nonnegative, since <math>a\ge c\ge e</math>. Their sum changes from <math>a+c+e</math> to <math>a+c-e</math>; it decreases as long as <math>e\ne 0</math>. 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 <math>a,c,e</math> has become a 0.
 +
 +
=== Case 2 ===
 +
<math>a,c>0</math> and <math>e=0</math>. 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 <math>2c-a</math> or <math>a-2c</math>. <math>a,c,0</math> is changed to either <math>c,2c-a,0</math> or <math>c,a-2c,0</math>. If we have <math>c,2c-a,0</math>, their sum is <math>3c-a</math> and this is less than <math>a+c+0</math> (the original sum) unless <math>a=c</math>, but <math>a\ne c</math> since the original sum <math>a+c+0</math> is odd by assumption. If we have <math>c,a-2c,0</math>, their sum is <math>a-c</math>, which is less than <math>a+c</math>. Operation B applied repeatedly will cause either <math>a</math> or <math>c</math> to become <math>0</math>.
 +
 +
=== Case 3 ===
 +
<math>a>0</math> and <math>c=e=0</math>. 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>
  
 
== Resources ==
 
== Resources ==

Revision as of 19:40, 18 December 2008

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]

Resources

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2003_USAMO_Problems/Problem_6&oldid=28631"