Absolute Value and 1998 integers

Here's Problem 1 from the 1998 USAMO:

Suppose that the set {1, 2, ..., 1998} has been partitioned into disjoint pairs {a_j, b_j}, j = 1, 2, ..., 999, so that for all j, |a_j - b_j| is either 1 or 6. Prove that the sum

|a₁ - b₁| + |a₂ - b₂| + ... + |a₉₉₉ - b₉₉₉|

ends in the digit 9.

Discussion

Suppose that the set {1, 2, ..., 1998} has been partitioned into disjoint pairs {a_j, b_j}, j = 1, 2, ..., 999, so that for all j, |a_j - b_j| is either 1 or 6. Prove that the sum

|a₁ - b₁| + |a₂ - b₂| + ... + |a₉₉₉ - b₉₉₉|

ends in the digit 9.

Solution 1

Let the number of pairs with |a_j - b_j| = 6 be m. Then the number of pairs with |a_j - b_j| = 1 is 999 - m. The sum of all the difference is

6m + (999 - m) = 5m + 999.

The statement will follow from the observation that m is necessarily even. This follows from a general property of partitions of the sets that comprise elements of two kinds.

Write the 1998 numbers in two rows with the designated pairs in the same column. Think of odd numbers as blue and of even numbers as red. If two numbers in the same column are of the same color join them by a line of that color. There will be as many blue lines as there are red lines. In other words, there are as many odd/odd pairs as there are even/even pairs.

In order that the difference of two numbers was even (6, in particular), the two numbers must have the same parity. It thus follows that the number of pairs whose difference is 6 is indeed even, and we are done.

One natural generalization of the problem is to prove that if 1998 is replaced with, say, 2L, then the difference

|a₁ - b₁| + |a₂ - b₂| + ... + |a_L - b_L|

ends in the same digit regardless of the partition into the a, b pairs. In fact, it is not at all important that the integer are exactly 1, 2, ..., 2L. Any set of 2L integers will do that admits a partition in which the absolute differences are 1 and 6. In this generality, 1 and 6 are not important in themselves, only the fact that their difference is 5 is. Say, if the absolute differences were 3 and 8 then, letting m to be the number of even differences, we would have

8m + 3(999 - m) = 5m + 2997,

from which the sum in question would be bound to end with the digit 7.

Solution 2

If necessary, by swapping a_j and b_j, we may assume that a_j > b_j so that

|a_j - b_j| = a_j - b_j.

The sum in question is then A - B, where A = ∑a_j and B = ∑b_j. Now, A + B = 1998·1999/2 is an odd number. If A - B = X, then X = A + B - 2B, making X also odd. This implies that the number of odd differences, say k, in X is odd and the number of the remaining ones (999 - k) is even. Letting m = 999 - k, we conclude with the same argument as in the previous solution.

References

A Decade of the Berkeley Mathematical Circle, The American Experience, Volume I, Z. Stankova, Tom Rike (eds), AMS/MSRI, 2008, pp. 82-83

Absolute Value

71876253