## Consequences of Getting More Than a Half

If more than half of the integers from {1, 2, ..., 2n} are selected, then some two of the selected integers are mutually prime.

Solution If more than half of the integers from {1, 2, ..., 2n} are selected, then some two of the selected integers are mutually prime.

Form pairs of consecutive integers:

 (1, 2), (3, 4), ..., (2n - 1, 2n).

There are n such pairs. By the Pigeonhole Principle, there is at least one pair with two selected integers. But these then differ by 1 and, hence, are mutually prime.

(This proof has been found by Paul Erdös' protege, Louis P´sa when he was 12 years old. See [Honsberger, pp. 10-21].)

### Reference

1. C. Alsina, R. B. Nelsen, Charming Proofs, MAA, 2010, p. 45
2. B. Bollobás, The Art of Mathematics: Coffee Time in Memphis, Cambridge University Press, 2006, p. 48.
3. R. Honsberger, Mathematical Gems, MAA, ### Related materialRead more...

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