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
re(2): Idea, no proof by Jer)
Your second example is fine.
If 3k = 126, then there are 63 odd numbers, plus {4, 12, 16, 20, 28, 36, 44, 48, 52, 60, 64, 68, 76, 80, 84, 92, 100, 108, 112, 116, 124} = 21 for a total of 84, more than 126/3*2-1 = 83, so you are good.
In fact my earlier post (3) was in error, because I used (n-1), n/4-1).. rather than (n), (n/4), so my examples should have been:
say n=128, then (n)+(n/4)+(n/16)+(n/64)+(n/128) = 171, implying that m=256, and 256*2/3-1 = 169, which is ok.
say n=2^14, then(n)+(n/2^2)+(n/2^4)+(n/2^6)+(n/2^8)+(n/2^10)+(n/2^12)+(n/2^14) = 21845, implying that m= 32768, and 32768*2/3-1 = 21844, also ok.
say n=2^20, then (n)+(n/2^2)+(n/2^4)+(n/2^6)+(n/2^8)+(n/2^10)+(n/2^12)+(n/2^14)+(n/2^16)+(n/2^18)+(n/2^20)= 1398101, implying that m= 2097152,and 2097152*2/3-1 = 1398100, also ok.
modified in all cases for clarity as you requested in my later post(7).
Edited on May 3, 2022, 3:29 am
|
|
Posted by broll
on 2022-05-03 03:07:36 |
re(3): Idea, no proof
