More than half of the integers from {1, 2, ..., 2n}
If more than half of the integers from
Contact Front page Contents Up
Copyright © 19962018 Alexander Bogomolny
If more than half of the integers from
[Bollobás]. Form the n sets
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
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 © 19962018 Alexander Bogomolny71766693
Related material
