No Averages

Here is an old Olympiad problem:

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.

Share:facebooktwittergoogle_plusredditpinterestlinkedinmail

5 Comments

  1. λ:

    Why 2^k? It seems, one should be able to pick (3^k-1)/2 such elements (with k=1 as special case).

  2. Leo:

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

  3. 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
    [1, 2, 4, 5, 10, 11, 13, 14, 28, 29, 31, 32, 37, 38, 40, 41]

  4. 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”

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