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"
(→‎Solution)
Line 3: Line 3:
 
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.
 
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 ==
+
== Solution 1==
 
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>.
 
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>.
  
Line 106: Line 106:
 
label("Step 4",(15,-2),(0,0));
 
label("Step 4",(15,-2),(0,0));
 
</asy>
 
</asy>
 +
 +
==Solution 2==
 +
We will show that Bert can make a sequence of moves such that the sum of all six integers, which we will denote in order as <math>x_1, x_2, x_3, x_4, x_5, x_6</math> will only decrease until it equals zero.  Since each move involves an absolute value, no integer will ever be negative, so when the sum of all six equals zero, it follows that each integer itself also equals zero.
 +
 +
Assume that at some point Bert cannot make a move that will decrease the sum of the integers.  In other words, he can only make moves that either do not  change or increase the sum.  Choose an arbitrary integer to perform the move on, say <math>x_2</math>, and without loss of generality, let <math>x_3 \ge x_1</math>.  It follows that <math>x_3-x_1 \ge x_2</math> and <math>x_3 \ge x_2</math>.
 +
 +
Since every possible move will not decrease the sum of the integers, we also perform the move on <math>x_3</math>.  Because <math>x_3 \ge x_2</math>, we must have <math>x_4 \ge x_3</math> otherwise <math>x_3</math> will necessarily decrease when the move is performed.  So far we have <math>x_2 \le x_3 \le x_4</math>, and by repeating the same argument over and over, we will have <math>x_2 \le x_3 \le x_4 \le x_5 \le x_6 \le x_1 \le x_2</math> implying that <math>x_1=x_2=x_3=x_4=x_5=x_6=c</math>.  If <math>c>0</math>, then any move that Bert makes will obviously decrease the sum of the integers by creating a zero.  The sum will only stop decreasing once <math>c=0</math>.  Contradiction, so each time it will be possible for Bert to make a move that decreases the sum of the integers until they all eventually equal 0.
  
 
== Resources ==
 
== Resources ==

Revision as of 13:29, 12 July 2009

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 1

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]

Solution 2

We will show that Bert can make a sequence of moves such that the sum of all six integers, which we will denote in order as $x_1, x_2, x_3, x_4, x_5, x_6$ will only decrease until it equals zero. Since each move involves an absolute value, no integer will ever be negative, so when the sum of all six equals zero, it follows that each integer itself also equals zero.

Assume that at some point Bert cannot make a move that will decrease the sum of the integers. In other words, he can only make moves that either do not change or increase the sum. Choose an arbitrary integer to perform the move on, say $x_2$, and without loss of generality, let $x_3 \ge x_1$. It follows that $x_3-x_1 \ge x_2$ and $x_3 \ge x_2$.

Since every possible move will not decrease the sum of the integers, we also perform the move on $x_3$. Because $x_3 \ge x_2$, we must have $x_4 \ge x_3$ otherwise $x_3$ will necessarily decrease when the move is performed. So far we have $x_2 \le x_3 \le x_4$, and by repeating the same argument over and over, we will have $x_2 \le x_3 \le x_4 \le x_5 \le x_6 \le x_1 \le x_2$ implying that $x_1=x_2=x_3=x_4=x_5=x_6=c$. If $c>0$, then any move that Bert makes will obviously decrease the sum of the integers by creating a zero. The sum will only stop decreasing once $c=0$. Contradiction, so each time it will be possible for Bert to make a move that decreases the sum of the integers until they all eventually equal 0.

Resources

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