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

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

Copyright © 1996-2018 Alexander Bogomolny
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

- C. Alsina, R. B. Nelsen,
*Charming Proofs*, MAA, 2010, p. 45 - B. Bollobás,
*The Art of Mathematics: Coffee Time in Memphis*, Cambridge University Press, 2006, p. 48. - R. Honsberger,
*Mathematical Gems*, MAA,

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

Copyright © 1996-2018 Alexander Bogomolny