27th USAMO 1998

The sets {a₁, a₂, ... , a₉₉₉} and {b₁, b₂, ... , b₉₉₉} together contain all the integers from 1 to 1998. For each i, |a_i - b_i| = 1 or 6. For example, we might have a₁ = 18, a₂ = 1, b₁ = 17, b₂ = 7. Show that ∑₁⁹⁹⁹ |a_i - b_i| = 9 mod 10.

Solution

If |a_i - b_i| = 6, then a_i and b_i have the same parity, so the set of such a_i and b_i contains an even number of odd numbers. But if |a_i - b_i| = 1, then a_i and b_i have opposite parity, so each such pair includes just one odd number. Hence if the number of such pairs is even, then the set of all such a_i and b_i also has an even number of odd numbers. But the total number of a_i and b_i which are odd is 999 which is odd. Hence the number of pairs with |a_i - b_i| = 1 must be odd, and hence the number of pairs with |a_i - b_i| = 6 must be even. Suppose it is 2k. Then ∑ |a_i - b_i| = (999 - 2k) 1 + 2k 6 = 999 + 10k = 9 mod 10.

27th USAMO 1998

© John Scholes
jscholes@kalva.demon.co.uk
11 May 2002