A bag contained balls numbered , and then students each took one ball from the bag. It turned out that none of the drawn numbers was exactly twice as big as any other drawn number. Determine the maximum possible . (Ana Prlić)
Solution
Group the observed numbers into sets:
The number of elements of is , for .
Notice that, for each , numbers and belong to and respectively for some . If all numbers from the sets and are drawn, the number of these numbers is and none of them is twice as big as any other.
Let us show that it is not possible to choose more than numbers that satisfy the condition. Let numbers from be drawn, for .
Observe the sets and . For every , is in . The number of these pairs is . Clearly at most one number is drawn from every pair. Except those numbers, set has another odd numbers, so at most numbers are drawn from and .
That means that .
Adding up those inequalities we get . Thereby the maximum possible is .
Want a route through all this instead of an archive? The track
puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.