2003 USAMO Problems/Problem 6

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

Page

Toolbox

Search