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.
[Bollobás]. 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:
{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.
[Sharygin]. In the set {1, 2, ..., 2n} there are n even and n odd integers. Let A consist of at least n + 1 numbers from that set: |A| > n. Every integer is a product of a power of 2 and an odd integer. Remove the powers of two from the members of A. The resulting set B consists of odd integers and, in addition, |B| = |A| > n. The terms of B are among the n odd members of the set {1, 2, ..., 2n}, meaning that some two of them must be equal. Of the corresponding terms of A, the smaller divides the larger, for the two are in the form 2kb, 2mb, with b odd and k ≠ m.
Reference
- B. Bollobás, The Art of Mathematics: Coffee Time in Memphis, Cambridge University Press, 2006, p. 48.
- I. F. Sharygin, Mathematical Mosaic, Mir, 2002, problem 65.3 (in Russian)
