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


|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

  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,

[an error occurred while processing this directive]

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

Copyright © 1996-2018 Alexander Bogomolny
[an error occurred while processing this directive]
[an error occurred while processing this directive]