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)
 
(One intermediate revision by one other user not shown)
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]]
 +
{{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"