Sum of Integers

Let n be a positive integer greater than 3. Let m be the largest integer in (n + 2)/2. Then, given more than m of the integers in the set {1, 2, ..., n}, some three of the integers in the given set have the property that one of the three is the sum of the other two.

Solution


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

Copyright © 1996-2017 Alexander Bogomolny

Let n be a positive integer greater than 3. Let m be the largest integer in (n + 2)/2. Then, given more than m of the integers in the set {1, 2, ..., n}, some three of the integers in the given set have the property that one of the three is the sum of the other two.
Let n be a positive integer greater than 3. Let m be the largest integer in (n + 2)/2. Then, given more than m of the integers in the set {1, 2, ..., n}, some three of the integers in the given set have the property that one of the three is the sum of the other two.

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

Related material
Read more...

  • More than half of the integers from {1, 2, ..., 2n}
  • Consequences of Getting More Than a Half
  • Remainder Multiples of 1997
  • Intersecting Subsets
  • Over-The-Counter Pigeonhole
  • Women in a theatre: Pigeonhole Principle
  • Pigeonhole Among Friends
  • Not Exceeding 24

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

    Copyright © 1996-2017 Alexander Bogomolny

     61236438

    Search by google: