# 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

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]$