Out of first 20,000 integers {1,2,3, ...20.000} is it possible to choose 500?

Question

such that no one is equal to arithmetic mean of any other two?

Answer 1

Nice.

Yes fortunately (since proving the affirmative requires only an example). It's equivalent to finding a set of one dimensional lattice points such that the midpoint of any pair of points is not in the set.

Edit: (the original example I gave requires only the numbers 1,2...,9843 but it's not as simple to prove) Define inductively:

S_0 = x
S_1 = x0x
S_2 = x0x 000 x0x
S_3 = x0x000x0x 000000000 x0x000x0x
...
S_(k+1) = S_k Z S_k
...

where x represents a position occupied by an element in the set and 0 represents an empty position. If S_k has the property that the midpoint of any two elements p,q is not in the set then S_(k+1) also has the property. This is by the inductive hypothesis if p,q are in the same copy of S_k, otherwise if p and q are in different copies of S_k then their midpoint lies in the empty middle third.

S_k has width 3^k and 2^k elements in it, so S_9 has width 3^9 = 19683 < 20000 and has 2^9 = 512 elements in it.

Answer 2

I think the sequence of triangular numbers, n(n+1)/2 for n>0, may be the densest set that satisfies the mean requirement, but there are only 199 numbers in that range, so no.

Answer 3

so we need to have five hundred numbers and no combination of any integer k and any integer n such that k, k+n, k-n belong to the five hundred.

Everytime we choose one number(k) we eliminated on possibiliety(either k+1 or k-1) and can still use the other.

Thus in choosing five hundred numbers we would have to eliminate five hundred numbers.

for instance
choose 2
eliminate 1
choose 3
eliminate4
choose 5
eliminate 6
Thus you get the pattern 2+3+5+7 and all odd numbers until you reach 500 numbers.

I guess it would be easier to say. The mean of any two odd numbers is even. Therefore in a set off all odd numbers one is never the mean of any other two.