## 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 _{j}, b_{j}},_{j} - b_{j}|

|a_{1} - b_{1}| + |a_{2} - b_{2}| + ... + |a_{999} - b_{999}|

ends in the digit 9.

|Contact| |Front page| |Contents| |Algebra|

Copyright © 1996-2018 Alexander Bogomolny

Suppose that the set {1, 2, ..., 1998} has been partitioned into disjoint pairs _{j}, b_{j}},_{j} - b_{j}|

|a_{1} - b_{1}| + |a_{2} - b_{2}| + ... + |a_{999} - b_{999}|

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 _{j} - b_{j}| = 1

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_{1} - b_{1}| + |a_{2} - b_{2}| + ... + |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

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 _{j} > b_{j}

|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,

### References

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

|Contact| |Front page| |Contents| |Algebra|

Copyright © 1996-2018 Alexander Bogomolny