| |
If more than half of the integers from {1, 2, ..., 2n} are selected, then some two of the selected integers have the property that one divides the other.
|
Form the n sets Ai = {2p(2i - 1)}, consisting of the ith odd integer less than 2n together with its multiples by powers of 2. Then the union of these n sets contains {1, 2, ..., 2n}. Hence some two of the selected integers belong to Ai, for some i; and so one of them divides the
other.
Example
Let n = 10. Numbers from 1 through 20 are split into 10 sets:
| |
{1, 2, 4, 8, 16}, {3, 6, 12}, {5, 10, 20}, {7, 14}, {9, 18},
{11}, {13}, {15}, {17}, {19}
|
The last 5 are a waste. In the worst case scenario, the first 5 selected numbers may fall into these sets without a hope of ever being paired with another number. Any two numbers in any of the remaining 5 sets would serve the purpose: one will divide the other. But, in the worst case, before getting two numbers in a single set, we may have to put one number into each of the five. With eleven numbers (20/2 + 1) we are sure that some two will fall into one of the first five sets.
Reference
- B. Bollobás, The Art of Mathematics: Coffee Time in Memphis, Cambridge University Press, 2006, p. 48.
Copyright © 1996-2008 Alexander Bogomolny
|
