Sum of Integers

Solution

|Contact| |Front page| |Contents| |Up| |Store|

The proof is by William A McWorter Jr..

Induction on n. Brute force shows that the result is true for n = 4 and n = 5.

Assume the result for n > 4. If (n + 1) is odd, then the greatest integer in (n +1 + 2)/2 is (n/2 + 1). If the more than (n/2 + 1) selected integers don't contain (n + 1), then the result follows because we've assumed the result holds for n.

Otherwise, the selected set contains (n + 1). Form the n/2 pairs {a, n + 1 - a}, for a = 1, ..., n/2. Then some two of the remaining at least (n/2 + 1) selected integers belong to one pair. Those two sum to (n + 1), one of the selected integers.

If (n + 1) is even, then the greatest integer in (n + 1 + 2)/2 is (n + 3)/2. Hence, if more than (n + 3)/2 integers are selected, more than (n + 1)/2 must be selected from {1, 2, ..., n}. By induction, some three of those selected from {1, 2, ..., n} must contain three with the property that one is the sum of the other two.

Here is another proof.

Let m be the largest integer in (n + 2)/2 and let x be the smallest of the m + 1 selected integers. Form the m differences between x and the other selected integers. We claim that one of these m differences is a selected integer other than x, thus showing that some selected integer is the sum of two other selected integers. To see this, the differences are, of course, between 1 and n. There are n - (m + 1) unselected integers plus the integer x. That's n - m integers. But m > n-m because 2m > n. Hence one of the differences must be a selected integer other than x.

References

1. B. Bollobás, The Art of Mathematics: Coffee Time in Memphis, Cambridge University Press, 2006, p. 110

|Contact| |Front page| |Contents| |Up| |Store|