Can you create a subset of (1, 2, 3, ..., 3k) such that none of its 2k-1 members is twice the value of another?
Either provide such a set or show none exists.
Inspired by: Austrian-Polish Math. Competition.
Greedily choosing numbers from the highest number down would seem to do the trick:
Consider k=33. We want a subset of 65 numbers from 1-99.
Include all of 99 down to 50 (50 numbers)
Exclude 49 to 25
Include all of 24 down to 13 (12 numbers)
Exclude 12 to 7
Include all of 6, 5, 4 (3 numbers)
Exclude 3, 2
Include 1 (1 number)
This is actually a set of 66.
This works because the sizes of the intervals are roughly 1/2+1/8+1/32... of 99 which approaches 2/3.
I see no reason this wouldn't work for all k but haven't proved it.
|
|
Posted by Jer
on 2022-05-02 07:32:24 |
Idea, no proof
