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.
The original question was:
Is there a 2000-element subset A of {1,2,...,3000} with the property that 2x is not in A whenever x is in a A? (Austrian-Polish Math. Competition, 1987)
Why choose 3000?
By far the majority of the results of adding INT(3k/2) (plus 1 for 3k odd) to the numbers in OEIS A108269 that are less than (3k) and then deducting (2k-1) are 1 though a result of 2 is also possible.
But very occasionally the result can be 0. The smallest such case is k=27 but there is also a run of 3 such cases at k=56-58. Overall, however there are only 8 such cases from k=1 to 172.
Let's look at 3000: 1500 candidates are immediately available as earlier discussed. Then we look for the largest entry in OEIS A108269 that is less than 3000; it is the 499th entry, 2996.
1500+499 = 1999 so no subset A is possible. Equivalently, the result of the computation mentioned above would be 0, that exceptional case.
Add to this that numbers of form (2*m - 1)*4^n lack a straightforward closed form, and the original question was quite ingenious.
Edited on May 3, 2022, 7:46 am
|
|
Posted by broll
on 2022-05-03 06:16:53 |
A final note on the original question
