Encuentre $2^k$ elementos del conjunto ${0,1,\cdots,3^k-1}$ tal que ninguno de estos elementos sea la media de otros dos elementos de $T$ .

Question

El problema es: Considere el conjunto $S = \{0, 1, 2, \ldots, 3^k-1\}$ . Demostrar que se puede elegir $T$ para ser un $2^k$ -subconjunto de elementos de $S$ tal que ninguno de los elementos de $T$ puede representarse como la media aritmética de dos elementos distintos de $T$ .

He representado los números en base $3$ ,luego he probado en casos pequeños y creo que todos los números(en base $3$ ) con $k$ número de dígitos positivos satisfacen el problema. Pero no sé cómo puedo demostrarlo. ¿Puede alguien ayudarme a demostrarlo?

Answer 1

Dejemos que $T$ sean los números cuya expansión de base 3 no tiene 1. Entonces demuestre que dados dos números distintos en $T$ su media aritmética tiene un 1 en su expansión de base 3.

Answer 2

Para $n=1,2$ elegir $0,1,3,4$ funciona.

Inducción:

Nuestra hipótesis de inducción será más fuerte que el resultado deseado:

Podemos elegir $2^k$ números inferiores a $\dfrac{3^k-1}2$ , tal que no haya tres de ellos de una secuencia aritmética.

La comprobación de los casos base es trivial.

Ahora, supongamos que tenemos $2^k$ números inferiores a $\dfrac{3^k-1}2$ , tal que no haya tres de ellos de una secuencia aritmética. Sea $a_1<a_2<\cdots<a_{2^k}$ sean esos números. Entonces, defina $a_{2^k+i}=3^k+a_i$ . Claramente $a_{2^{k+1}}\le 3^k+\dfrac{3^k-1}2=\dfrac{3^{k+1}-1}2$

Como $a_{2^k+i}$ s son una traducción de $a_i$ s no formarán una secuencia aritmética entre ellos. Además, $$\frac12(a_{2^k+j}+a_i)=\frac12(3^k+{a_i+a_j})\le \frac12(3^k+{\dfrac{3^k-1}2+\dfrac{3^k-1}2})\le 3^k-1$$ $$\frac12(a_{2^k+j}+a_i)=\frac12(3^k+{a_i+a_j})\ge \frac123^k\ge \frac{3^k-1}2$$

Así, $$a_{2^k}<\frac12(a_{2^k+j}+a_i)<a_{2^k+1}$$

Por lo tanto, no hay progresiones aritméticas, donde el número más pequeño es de $a_1,\cdots,a_{2^k}$ y el mayor término es de $a_{2^k+1},\cdots,a_{2^{k+1}}$ . Así, $a_1,\cdots,a_{2^{k+1}}$ no contiene ninguna progresión aritmética. La inducción ha terminado.

Answer 3

En efecto, consideremos el conjunto de números en los que cada dígito en base 3 es 1 o 2.

Dejemos que $a,b$ sean dos números de este tipo con la misma paridad y supongamos que coinciden en el último $r$ posiciones y difieren en el $(r+1)$ de la derecha.

Entonces $a=\ldots 1 x x \ldots x$ y $b= \ldots 2 x x \ldots x$ en base 3. Entonces su media tiene $x$ en el último $r$ posiciones y tiene un cero en el $(r+1)$ posición de la derecha. Para ver esto, dejemos $A,B$ sean los números obtenidos al eliminar el último $r$ dígitos de $a,b$ resp. Entonces la base 3 rep de $(a+b)/2$ es sólo la base 3 rep de $(A+B)/2$ seguido de $r$ de la $x$ s. Desde $A+B$ es divisible por 3, la conclusión es la siguiente.