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 1==
+
== 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>.
 
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 ===
 
=== Case 1 ===
 
<math>a,c,e>0</math>. Define ''Operation A'' as the sequence of moves from Step 1 to Step 3, shown below:
 
<math>a,c,e>0</math>. Define ''Operation A'' as the sequence of moves from Step 1 to Step 3, shown below:
<asy>
+
<center><asy>
 
size(300);
 
size(300);
 
defaultpen(fontsize(9));
 
defaultpen(fontsize(9));
Line 34: Line 34:
 
label("$a-c$",(10,0)+expi(5*pi/3),(0,0),red);
 
label("$a-c$",(10,0)+expi(5*pi/3),(0,0),red);
 
label("Step 3",(10,-2),(0,0));
 
label("Step 3",(10,-2),(0,0));
</asy>
+
</asy></center>
 
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.
 
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 ===
 
=== 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:
 
<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>
+
<center><asy>
 
size(300);
 
size(300);
 
defaultpen(fontsize(9));
 
defaultpen(fontsize(9));
Line 66: Line 66:
 
label("$0$",(10,0)+expi(5*pi/3),(0,0),red);
 
label("$0$",(10,0)+expi(5*pi/3),(0,0),red);
 
label("Step 3",(10,-2),(0,0));
 
label("Step 3",(10,-2),(0,0));
</asy>
+
</asy></center>
 
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>.
 
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 ===
 
=== 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:
 
<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>
+
<center><asy>
 
size(400);
 
size(400);
 
defaultpen(fontsize(9));
 
defaultpen(fontsize(9));
Line 105: Line 105:
 
label("$0$",(15,0)+expi(5*pi/3),(0,0),red);
 
label("$0$",(15,0)+expi(5*pi/3),(0,0),red);
 
label("Step 4",(15,-2),(0,0));
 
label("Step 4",(15,-2),(0,0));
</asy>
+
</asy></center>
  
==Solution 2==
+
== See also ==
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.
+
{{USAMO newbox|year=2003|num-b=5|after=Last question}}
 
 
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 ==
 
 
 
* [[2003 USAMO Problems]]
 
 
* [http://www.artofproblemsolving.com/Forum/viewtopic.php?t=53673 Discussion on AOPS/MathLinks]
 
* [http://www.artofproblemsolving.com/Forum/viewtopic.php?t=53673 Discussion on AOPS/MathLinks]
  
 
[[Category:Olympiad Combinatorics Problems]]
 
[[Category:Olympiad Combinatorics Problems]]

Revision as of 16:48, 17 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

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 (ProblemsResources)
Preceded by
Problem 5
Followed by
Last question
1 2 3 4 5 6
All USAMO Problems and Solutions