Absolute Value and 1998 integers

Here's Problem 1 from the 1998 USAMO:

Discussion

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

Copyright © 1996-2012 Alexander Bogomolny

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

1. 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

• Absolute Value
• Importance of the Absolute Value
• Cartesian Coordinate System
• Algebraic Structure of Complex Numbers
• Structure of Hyperreal Numbers
• Farmer and Wife To Catch Rooster and Hen
• Topological Preliminaries
• Proizvolov's Identity
• Absolute Value and 1998 integers

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

Copyright © 1996-2012 Alexander Bogomolny