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 Bogomolny71537193