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

If more than half of the integers from

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

Copyright © 1996-2018 Alexander Bogomolny
If more than half of the integers from

[Bollobás]. Form the n sets _{i} = {2^{p}(2i - 1)},^{th} odd integer less than 2n together with its multiples by powers of 2. Then the union of these n sets contains _{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

[Sharygin]. In the set {1, 2, ..., 2n} there are n even and n odd integers. Let A consist of at least ^{k}b, 2^{m}b, with b odd and

### 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)

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

Copyright © 1996-2018 Alexander Bogomolny