USAMO 03/B3 solution

33rd USAMO 2003

Problem B3

A positive integer is written at each vertex of a hexagon. A move is to replace a number by the (non-negative) difference between the two numbers at the adjacent vertices. If the starting numbers sum to 2003²⁰⁰³, show that it is always possible to make a sequence of moves ending with zeros at every vertex.

Solution

It is possible to get stuck, so the result is not trivial. For example:

  1 1
0     0
  1 1

We show that provided the sum of the numbers is odd, we can always find a sequence of moves which give either (1) a lower maximum number, and odd sum, or (2) all zeros. Since the starting sum is odd, that is sufficient.

Note that no move increases the maximum. The first step is to show that if the sum is odd, we can find moves which give just one number odd. For convenience we refer to the numbers as

  A B
F     C
  E D

We also use the letters to refer to moves. So, for example, B means the move replacing B. Since the sum is odd, either A+C+E is odd or B+D+F is odd. wlog A+C+E is odd. Suppose just one of A,B,C is odd. wlog it is A. Making the moves B, F, A, F, D and working mod 2 we get successively:

  1 B       1 1       1 1       0 1       0 1       0 1
F     0   F     0   1     0   1     0   0     0   0     0
  0 D       0 D       0 D       0 D       0 D       0 0

Similarly, if all of A, B, C are odd, then B, F, D, E, C we get mod 2:

  1 B       1 0       1 0       1 0       1 0       1 0
F     1   F     1   0     1   0     1   0     1   0     0
  1 D       1 D       1 D       1 0       0 0       0 0

So wlog A is odd and all the other numbers are even. Suppose that the maximum is M. We show how to reduce M. There are two cases. Suppose first that M is even so that A < M. Then we make the moves B, C, D, E, F giving (mod 2):

  1 0       1 1       1 1       1 1       1 1       1 1
0     0   0     0   0     1   0     1   0     1   0     1
  0 0       0 0       0 0       0 1       1 1       1 1

The first four moves do not change A, which is neither 1 nor M, so the last move must reduce F, so the new maximum must be an odd number. But it must be ≤M, which is even, so the new maximum is <M and the sum is still odd.

The second case is M odd, so that A = M. If C > 0 we make the moves B, F, A, F giving (mod 2):

  1 0       1 1       1 1       0 1       0 1
0     0   0     0   1     0   1     0   0     0
  0 0       0 0       0 0       0 0       0 0

Since C is not 0 or M, the new B must be <M and the other new numbers are all even and hence <M. So the new maximum is <M and the sum is still odd. The same argument works if E > 0 (just reflect about AD). So finally suppose C = E = 0. Then we get (no reduction mod 2):

  A B       A A       A A       A A       A A       0 A       0 A       0 0
F     0   F     0   A     0   A     0   A     0   A     0   0     0   0     0
  0 D       0 D       0 D       0 D       0 0       0 0       0 0       0 0

33rd USAMO 2003