USAMO 94/2 solution

23rd USAMO 1994

Problem 2

The sequence a₁, a₂, ... , a₉₉ has a₁ = a₃ = a₅ = ... = a₉₇ = 1, a₂ = a₄ = a₆ = ... = a₉₈ = 2, and a₉₉ = 3. We interpret subscripts greater than 99 by subtracting 99, so that a₁₀₀ means a₁ etc. An allowed move is to change the value of any one of the a_n to another member of {1, 2, 3} different from its two neighbors, a_n-1 and a_n+1. Is there a sequence of allowed moves which results in a_m = a_m+2 = ... = a_m+96 = 1, a_m+1 = a_m+3 = ... = a_m+95 = 2, a_m+97 = 3, a_n+98 = 2 for some m? [So if m = 1, we have just interchanged the values of a₉₈ and a₉₉.]

Solution

This is a classic invariant problem. We strongly suspect that there is no sequence of moves (otherwise it would be too easy to find), so that we must prove there is no sequence. The standard approach is to look for some invariant which is not changed by the allowed moves, but which is different for the initial and desired final positions.

For each member a_i of the sequence let b_i =
0 if a_i = a_i+1,
1 if (a_i, a_i+1) = (1, 2) , (2, 3) or (3, 1)
-1 if (a_i, a_i+1) = (1, 3), (2, 1) or (3, 2).

We hope that b₁ + b₂ + ... + b₉₉will be a suitable invariant. Suppose we make an allowed move by changing a_i. That has the effect of changing just b_i-1 and b_i. If a_i-1 = a_i+1, then b_i-1 + b_i = 0, so the total of the b_j does not change. If a_i-1 does not equal a_i+1, then we cannot change a_i since it must be different from both. Thus allowed moves do not change b₁ + ... + b₉₉. So it is an invariant. We now check it is suitable. The initial value is + 3 (there are 49 pairs (1,2), 48 pairs (2,1), 1 pair (2,3) and 1 pair (3,1) total 49 - 48 + 1 + 1 = 3. But the desired final position has value -3 (it has 48 pairs (1, 2), 49 pairs (2, 1), 1 pair (1, 3) and 1 pair (3, 2), total 48 - 49 - 1 - 1 = - 3). So we cannot get from one to the other by allowed moves.

23rd USAMO 1994