Prove that you can choose 2^{k} numbers from the set {1, 2, 3, …, 3^{k}−1} in such a way that the chosen set contains no averages of any two of its elements.

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”

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.
By 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.

## λ:

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 pm## Leo:

E.g. all numbers in the given range not having digit 1 in their ternary representation, and 1000…0000.

26 June 2014, 9:14 pm## lvps1000vm:

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 am## wonder:

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.