More than half of the integers from {1, 2, ..., 2n}

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.

Solution

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 A_i = {2^p(2i - 1)}, consisting of the i^th 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 A_i, 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.

[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 2^kb, 2^mb, 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)

72099564