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.
(In reply to
Idea, no proof by Jer)
As an approximation for testing purposes:
For even m, say (2n), then (n+1) to (2n) (total:n-1) are in, and (n/4)+1 to (n/2) are in (total: (n/4-1)), and (n/16)+1 to (n/8) (total: (n/16-1)) are in etc.
say n=128, then (n-1)+(n/4-1)+(n/16-1)+(n/64-1)+(n/128-1) = 166, implying that m=256, but then 256*2/3-1 = 169, so there are insufficient numbers to choose from.
say n=2^14, then(n-1)+(n/2^2-1)+(n/2^4-1)+(n/2^6-1)+(n/2^8-1)+(n/2^10-1)+(n/2^12-1)+(n/2^14-1) = 21837, implying that m= 32768, but then 32768*2/3-1 = 21844.
say n=2^20, then(n-1)+(n/2^2-1)+(n/2^4-1)+(n/2^6-1)+(n/2^8-1)+(n/2^10-1)+(n/2^12-1)+(n/2^14-1)+(n/2^16-1)+(n/2^18-1)+(n/2^20-1)= 1398090, implying that m= 2097152, but then 2097152*2/3-1 = 1398100, and the shortfall is increasing.
|
|
Posted by broll
on 2022-05-02 09:35:53 |
re: Idea, no proof
