No Averages
Here is an old Olympiad problem:
Share:Prove that you can choose 2k numbers from the set {1, 2, 3, …, 3k−1} in such a way that the chosen set contains no averages of any two of its elements.
Tanya Khovanova's Math Blog
Mathematics, applications of mathematics to life in general, and my life as a mathematician.
Follow Me
λ:
Why 2^k? It seems, one should be able to pick (3^k-1)/2 such elements (with k=1 as special case).
26 June 2014, 12:44 pmLeo:
E.g. all numbers in the given range not having digit 1 in their ternary representation, and 1000…0000.
26 June 2014, 9:14 pmlvps1000vm:
I can restrict it to finding 2^k numbers from the set {1 … ((3^k)+1)/2}.
In Python:
def subset_no_averages(k):
….s = [1]
….for i in range(k):
……..extra = s[-1] * 2 – 1
……..s = s + [x + extra for x in s]
….return s
Example, k = 4
27 June 2014, 9:04 am[1, 2, 4, 5, 10, 11, 13, 14, 28, 29, 31, 32, 37, 38, 40, 41]
lvps1000vm:
I noticed that my proposed algorithm it’s similar to what Leo proposed, as it’s “numbers whose ternary representation does not contain number TWO, plus one”
27 June 2014, 9:19 amwonder:
Do it recursively:
For k = 1 we can just pick 1 and 2.
Suppose we have an answer for k with elements {a_1, a_2, … a_{2^k}}.
Construct a solution for k + 1 elements with {a_1, a_2, … a_{2^k}, a_1 + d, a_2 + d, … a_{2^k} + d}, where d = 3^{k+1} – 3^k.
Essentially we have two sets of elements S1 and S2, with S2 offset by d from S1.
Now we pick two numbers from these.
8 July 2014, 5:24 amBy the construction, if both numbers are from S1 or both are from S2, then we are already done.
If one is from S1 and the other from S2, then their average is within the ‘gap’ of size d that we have created here.