OFO 2021 Problema 11

[Gianni De Rico]

Sea $n$ un entero positivo. Inicialmente en el pizarrón están escritos los números $0,1,2,\ldots ,n-1,n$. En cada paso, Francesco elige un número del pizarrón que sea igual al promedio de otros dos números que están escritos en el pizarrón y lo borra. Continúa haciendo esto hasta que sea imposible hacer más pasos. Determinar, para cada valor de $n$, cuál es la mínima cantidad de números que pueden quedar escritos en el pizarrón al final del proceso.

[Gianni De Rico]

Solución Oficial:

Spoiler: mostrar

Vamos a ver que la respuesta es $2$ cuando $n$ es una potencia de $2$, y $3$ en otro caso.

Notemos primero que siempre tendremos al menos dos números en el pizarrón, ya que nunca podremos borrar a $0$ ni a $n$.

Sea $n=2^k$, con $k$ entero no negativo, veamos por inducción en $k$ que siempre podemos dejar únicamente a $0$ y $2^k$ en el pizarrón.
El caso base $k=0$ es claramente cierto, ya que los únicos números escritos en el pizarrón son $0$ y $1$.
Supongamos como hipótesis inductiva que podemos borrar todos los números entre $0$ y $2^k$. Para borrar todos los números entre $0$ y $2^{k+1}$ borramos primero todos los números entre $0$ y $2^k$ (que podemos por hipótesis inductiva), y después realizamos exactamente las mismas operaciones en la lista de números $2^k,2^k+1,2^k+2,\ldots 2^{k+1}-1,2^{k+1}$, que es la misma que la lista $0,1,2,\ldots ,2^k-1,2^k$ pero sumándole $2^k$ a todos, por lo que también se le suma $2^k$ al promedio de cada par. Entonces nos quedan los números $0,2^k,2^{k+1}$ escritos en el pizarrón, y podemos borrar a $2^k$.
Otra forma de hacer esto sería pensar todos los números de la lista en binario y en cada paso eliminar los que tengan un $1$ más a la derecha (es decir, eliminar primero todos los impares, después todos los múltiplos de $2$ pero no de $4$, después los múltiplos de $4$ pero no de $8$, y así).

Sea $n=2^k+t$, con $0<t<2^k$ (es decir, $2^k$ es la mayor potencia de $2$ menor que $n$). Vamos a mostrar una forma de dejar únicamente los números $0,2^k,2^k+t$ en el pizarrón.
Escribimos cada número entre $2^k$ y $2^k+t$ como $2^k+t-r$, con $0<r<t$, los vamos a ir eliminando en orden decreciente (primero $2^k+t-1$, después $2^k+t-2$, y así). Notemos que $2^k+t-r$ es el promedio entre $2^k+t$ y $2^k+t-2r$. Como $r<t$, entonces $2^k+t-2r>2^k+t-2t=2^k-t>0$; y como $r>0$, entonces $2^k+t-2r<2^k+t-r$. En resumen, $0<2^k+t-2r<2^k+t-r$, entonces por el orden en el que estamos borrando los números, tenemos que $2^k+t-2r$ todavía está escrito a la hora de borrar $2^k+t-r$. De esta forma conseguimos que nos queden $0,1,2,\ldots ,2^k,2^k+t$, y de la misma forma que hicimos antes podemos eliminar todos los números entre $0$ y $2^k$, dejando únicamente $0,2^k,2^k+t$ en el pizarrón.

Veamos ahora que si $n$ no es potencia de $2$, siempre van a quedar al menos $3$ números escritos en el pizarrón. Para eso, notemos que si podemos llegar de $0,1,2,\ldots ,n-1,n$ a $0,n$ siguiendo los pasos del enunciado, entonces partiendo de $0,n$ podemos hacer los pasos opuestos y llegar a $0,1,2,\ldots ,n-1,n$.
Escribamos $n=2^km$ con $m$ impar, tenemos entonces que todos los números escritos ($0$ y $n$) son múltiplos de $m$, vamos a ver que si tenemos escritos todos múltiplos de $m$, solamente podemos agregar múltiplos de $m$. Si $x$ e $y$ son múltiplos de $m$ tales que su promedio es entero, podemos escribir $x=ma$, $y=mb$ y $\frac{x+y}{2}=p$, entonces $m(a+b)=x+y=2p$, de modo que $2p$ es múltiplo de $m$, pero como $m$ es impar, entonces $p$ es múltiplo de $m$.
Por lo tanto, partiendo de la lista $0,n$ podemos llegar únicamente a una lista con todos múltiplos de $m$, en particular, si podemos llegar a tener todos los números escritos, debemos escribir al $1$, entonces $1$ debe ser múltiplo de $m$, de modo que $m=1$. Es decir que si $n$ no es una potencia de $2$, no podemos llegar desde $0,n$ a tener todos los números escritos, de modo que nos deben quedar al menos $3$ números escritos al final.

Vimos entonces que si $n$ es potencia de $2$ nos deben quedar al menos dos números, y dimos una forma de lograrlo; vimos también que si $n$ no es potencia de $2$ nos deben quedar al menos $3$ números, y dimos una forma de lograrlo. Esto completa la demostración.

[joa.fernandez]

Solución:

Spoiler: mostrar

Sea $f(n)$ la mínima cantidad de números que pueden quedar escritos en el pizarrón.
Claramente $f(1)=2$, ya que no se puede borrar ningun número.
Como observación, sabemos que los números de las puntas ($0$, $n$) no se pueden borrar, ya que de lo contrario, existirían dos enteros positivos $i$, $j$ tales que $i+j=0$ o $i+j=2n$, pero $0<i,j<n$, de donde se llega a un absurdo.
De esto último notamos que $f(n)\geq 2$.
Además, notemos que los pasos son invertibles, es decir, si Francesco puede en un paso borrar a un número, es porque satisface que el promedio de otros dos números es igual al número. Al fin y al cabo, debido a esto podemos empezar (por ejemplo) con los números $1$ y $n$ y en cada paso agregar un número que satisfaga que es el promedio de otros dos que ya están en la lista.
Usando esto de la operación invertible, y suponiendo que los números escritos en algún momento son $a_1$, $a_2$, $a_3$, ..., $a_i$ tales que $a_1<a_2<a_3<...a_i$, llamo como pasazo a agregar a todos los números de la forma $\dfrac{a_t+a_{t+1}}{2}$. Es decir, si tenemos la lista ordenada, agrego todos los posibles números que son promedio de dos consecutivos. Si tengo $1,3,5,9$, después de un pasazo la lista me queda $1,2,3,4,5,7,9$. Notemos que no siempre se puede realizar un pasazo, ya que puede ocurrir que $a_t$ y $a_{t+1}$ tengan distinta paridad.

Ahora vamos a partir la solución en dos partes:
$f(2^k)$ con $k$ entero positivo arbitrario, y $f(n)$ con $n\neq 2^k$, siendo $k$ un entero positivo arbitrario.
Para lo primero, vamos a ver que vale $2$.

En efecto, supongamos que al final tenemos los números $0$ y $2^k$. Veamos cómo queda la lista luego de aplicar varios pasazos.
$0,2^k\Rightarrow 0,2^{k-1},2^k\Rightarrow 0,2^{k-2},2^{k-1},2^{k-2}+2^{k-1},2^k\Rightarrow ...$
Si somos observadores, podemos notar que los términos de la lista luego de cada pasazo siempre quedan en progresión aritmética. Esto lo podemos demostrar por inducción... Para el caso base, luego de un pasazo, tenemos que la lista es $0,2^{k-1},2^k$, por lo que la diferencia de la progresión es $2^{k-1}$ ($2^{k-1}+1+(2^{k-1})=2^k+1$), por lo que el caso base vale. Supongamos que para algún $t$ arbitrario vale que la diferencia de términos consecutivos de la lista luego de $t$ pasazos es $2^{k-t}$, veamos que, para el pasazo $t+1$:
Tomemos dos terminos consecutivos arbitrarios antes del pasazo, $a_i$ y $a_{i+1}$. Satisfacen que $a_{i+1}=a_i+2^{k-t}$. Al aplicar un pasazo, el nuevo término es $\dfrac{a_i + a_i+2^{k-t}}{2}= a_i + 2^{k-(t+1)}$. Y notemos que la diferencia entre estos tres números es exactamente $2^{k-(t+1)}$, como queríamos ver (como los dos términos del principio eran arbitrarios, vale para todos).
Entonces, al aplicar $k$ pasazos, la diferencia de términos consecutivos de la lista será $2^{k-(k)}=1$, es decir, se tendrán los números $0,1,...,2^k$, y como empezamos con $0$ y $2^k$, demostramos que $f(2^k)=2$.
Ahora vamos a demostrar que $f(n)\geq 3$ para $n\neq 2^k$.
En efecto, supongamos que $f(n)=2$.
Si $n$ fuera impar, los últimos dos números serían $0$ y $n$, pero $\dfrac{0+n}{2}$ no sería entero, por lo que llegamos a un absurdo, de donde $f(n)\geq 3$ en este caso.
Si $n$ fuera par, lo representamos como $t\cdot2^k$ con $t$ un entero positivo impar (en esencia, $2^k\mid \mid n$). Ahora, si al final se tienen los números $0,t\cdot 2^k$, es porque existe una sucesión de pasos que finalizan con estos dos números, por ende, existe una sucesión de pasos "inversa" que empieza con $0,t\cdot 2^k$ y finaliza con $0,1,2,...,t\cdot 2^k$. La observación clave para esto es que una sucesión de pasos inversa siempre deja una lista de números todos congruentes a $0\pmod{t}$. En efecto, si dos términos son congruentes módulo $t$, entonces su promedio también lo será, ya que $2\nmid t$, y como $0$ y $t\cdot 2^k$ son ambos congruentes a $0$ módulo $t$, la sucesión de pasos inversa siempre deja números divisibles por $t$ (funciona como un argumento inductivo pero mucho más elemental, ya que se usa el caso base y si se agrega un número también sigue valiendo la condición).
Entonces, a lo sumo se puede llegar a obtener la sucesión de números de $0,t,2t,...,t\cdot 2^k$ (todos los múltiplos de $t$ acotados entre $0$ y $t\cdot 2^k$) y como el $mcd(2,t)=1$, nunca se podría obtener este número, lo cual es un claro absurdo, de donde se sigue que $f(n)\geq 3$ en este caso.

Ahora queda lo fácil, ya que, si tenemos un número $n$ tal que no es de la pinta $2^k$, podemos tomar un $t$ tal que $2^t<n<2^{t+1}$. En un principio, Francesco puede eliminar los números $n-1,n-2,...,2^t+1$ en ese orden. En efecto, si debe borrar $l$ ($l$ dentro de ese conjunto de números), notemos que siempre tiene escrito aún el número $2l-n$ ya que $2l-n<l$ y además $2l-n>0$ ya que $l>2^t$ de donde efectivamente puede borrar $l$ (el promedio de esos dos números es $l$). Cuando queden los números $0,1,2,3,...2^t,n$, por lo anteriormente demostrado, puede eliminar los números $1,2,3,...,2^{t-1}$, de donde quedarían exactamente $3$ números, por lo que es el mínimo.

En síntesis, demostramos que $f(2^k)=2$ y $f(n)=3$ para $n\neq2^k$. Eso completa la resolución.

[EmRuzak]

Spoiler: mostrar

Como los dos números a los que se les hace el promedio para determinar si es posible sacar a un número $m$ son distintos de $m$, y su promedio es $m$, estos dos números son distintos entre sí.

Si se tiene la lista al final de las operaciones, haciendo una o varias veces la operación opuesta, es decir, elegir dos números y escribir el promedio de dos números, se puede llegar a la lista original.

Como los números $0$ y $n$ no son el promedio de dos números distintos de la lista, ya que son el menor y el mayor elemento, estos dos deben estar en la lista final.

Lema 1:
Si se puede obtener la lista $0,1,2...n$ con promedios a partir de la lista $a_1,a_2...a_m$, se puede obtener la lista
$k,k+1,k+2...k+n$ a partir de la lista $a_1+k,a_2+k...a_m+k$ ya que $(a+k+b+k)/2=(a+b)/2+k$ por lo que los
promedios son iguales a los de la lista anterior, pero sumados a $k$

Si $n$ es igual a $2^x$ con $x>=0$, y se tiene la lista $0,1,2..,n$, se puede obtener $n/2=n^{x-1}$, y se pueden crear $2$ listas, $0,1,2..,n^{x-1}$ y $n^{x-1},n^{x-1}+1...n^{x}$, que es igual a la otra lista pero sumada a $n^{x-1}$, como se puede obtener el promedio de $0$ y $n^x$ para $x>0$ y $2^(1-1)=1$, por inducción se puede obtener la lista $0,1,2...n$ a partir de $0$ y $n$, entonces en el caso de que $n$ sea una potencia de $2$ la mínima lista final contiene $2$ elementos

Si $n=2^xk$ con $k$ impar mayor a $1$ y $x>=0$, es decir que $n$ no es una potencia de $2$, la lista no se puede obtener a partir de $0$ y $n$ ya que $0$ y $n$ son múltiplos de $k$ y un promedio de dos múltiplos de $k$ es un múltiplo de $k$ ya que su suma es múltiplo de $k$ y sus factores primos excepto el $2$ se conservan, y como $k$ es impar no tiene ningún factor $2$, entonces la lista completa debería contener solo múltiplos de $k$, pero el $1$ no es múltiplo de $k$ y esta en la lista inicial por lo que para cualquier $n$ que no sea una potencia de $2$ se necesitan al menos $3$ elementos.

Si esos $3$ elementos son $0,1,n$, se puede obtener la lista completa de $0$ a $n$.
Si hacemos el promedio de $0$ y $n$ si $n$ es par y de $1$ y $n$ si $n$ es impar, se obtiene $\lceil n/2\rceil$, el cual es menor a $n$ para cualquier $n>1$, y es mayor o igual a $n$ solo si $n=1$ o $n=0$, y además no puede ser menor o igual a $0$ para cualquier $n>0$ por lo que al hacer repetidas veces la operación se llega al $1$, la única forma de llegar al $1$ con $n>1$ es con $n=2$ entonces se obtiene el $2$ en la lista después de hacer la operación repetidas veces.
entonces si se forma la lista $1,2...n$ que es $0,1...n-1$ sumada a $1$, se puede obtener el $3$ y así sucesivamente hasta llegar al $n$, por el lema 1

Entonces si $n$ es una potencia de $2$ incluido $n=1$ la menor cantidad de elementos en la lista final es $2$ y si no es $3$

[El gran Filipikachu;]

Spoiler: mostrar

En cualquier caso van a quedar al menos dos números, $0$ y $n$, ya que el promedio de ningún par de números nos da esos resultados.
Supongamos que se borraron todos los números exceptuando $0$ y $n$. En este caso, se puede hacer una reconstrucción, ya que hacemos el procedimiento inverso.
$0, ..., n$
$0, ..., \frac{n}{2}, ..., n$
$0, ..., \frac{n}{4}, ..., \frac{2n}{4}, ..., \frac{3n}{4}, ..., n$
$0, ..., \frac{n}{8}, ..., \frac{2n}{8}, ..., \frac{3n}{8}, ..., \frac{4n}{8}, ..., \frac{5n}{8}, ..., \frac{6n}{8}, ..., \frac{7n}{8}, ..., n$
Vemos que para cada $n$ el único valor posible es una potencia de 2, por lo que para toda potencia de 2 quedan 2 números sin borrar ($0$ y $n$).

Ahora lo que vamos a ver es que pasa cuando no son potencias de 2,
Tenemos la siguiente lista de números:
$0, ..., 2 ^x, ...., n$
En la lista hay una potencia de dos que es la mayor, podemos asegurar que $\frac{n}{2}<2^x<n$ ya que en caso contrario, $2^x$ no sería la mayor potencia de 2.

Sabemos que entre $0$ y $2^x$ podemos borrar todos los números excepto los que nombramos. Si queremos borrar los números entre $2^x$ y $n$ tenemos que encontrar la forma de borrarlo.
$n$ no puede ser borrado, $n-1$ se borra con ayuda de $n-2$, $n-2$ se borra con ayuda de $n-4$ y así sucesivamente borrando cada número $n-m$ con ayuda de $n-2m$ y $n$ (Siendo $n-m$ mayor que $2^x$).
Para borrar $2^x+1$ tendremos que usar $n$ y $2^{x+1}+2-n$.
$2^{x+1}+2-n$ es mayor a 0, ya que entre $0$ y $n$ la mayor potencia de 2 es $2^x$, por lo que $2^{x+1}$ es mayor que $n$ y por lo tanto, $2^x+1$ se puede borrar tranquilamente.
Nos quedan 3 números sin borrar, ya que primero se borran los números que están entre $2^x$ y $n$, y después los números entre $0$ y $2^x$.
¿Por qué en estos casos no pueden quedar 2 números sin borrar? Porque si fuera así, dicho caso se podría reconstruir teniendo $0$ y $n$, y sabemos que eso solo pasa con las potencias de 2.

[Felibauk]

Spoiler: mostrar

Lema: si $a \leq b$, entonces se cumple lo siguiente con su media: $a \leq \frac{a+b}{2} \leq b$ con igualdad sí y solo sí $a=b$.
Demostración: $\frac{a+b}{2} \geq \frac{a+a}{2} = \frac{2a}{2} = a$ y $\frac{a+b}{2} \leq \frac{b+b}{2} = \frac{2b}{2} = b$, por lo que en efecto $a \leq \frac{a+b}{2} \leq b$ y claramente la igualdad se da solo cuando $a=b$.

Ahora bien, vamos a pensar el problema "de forma inversa": trabajamos con los números enteros del $0$ al $n$, $n$ entero positivo. Nuestra operación es tomar dos números que estén escritos en el pizarrón y escribir su promedio (si es entero). Entonces la consigna es hallar para cada $n$ la mínima cantidad de números necesaria para que sea posible mediante la operación, escribir los números que faltan.

Notemos que inexorablemente tenemos que tener el $0$ y el $n$ inicialmente (si no, para agregarlos mediante la operación tendríamos que tener un número negativo y un número mayor o igual a $n+1$, respectivamente, lo cual no hay).

Propiedad: si tenemos el $0$, el $1$ y el $n$, podemos escribir los números restantes mediante una serie de operaciones y cumplir con nuestro objetivo.
Demostración:

Spoiler: mostrar

nuestra técnica va a ser conseguir escribir $c+1$ teniendo escritos anteriormente $0,1, \dots ,c$ y $n$. Lo veremos por inducción lógicamente:
.Caso base: tenemos escritos el $0$ y el $1$, $c=1$.
.Paso inductivo: teniendo escritos $0,1, \dots ,c$ y $n$, veremos que es posible conseguir el $c+1$ ($c+1 < n$): creamos una lista de números $d$ del siguiente modo: $d_{1}=\frac{n+c-1+\epsilon _{1}}{2}$ y $d_{i+1}=\frac{d_{i}+c-1+ \epsilon _{i+1}}{2}$, con $\epsilon _{i} \in \{0;1\}$, $\forall i \in \mathbb {N}$.
¿Qué quiere decir esto? Construimos el siguiente número de la lista con el promedio del anterior y $c-1$ o $c$ (según se requiera para que la media sea entera).
Por nuestro lema, como $c<n$, $c-1 + \epsilon _{1}<d_{1}<n$ y en general, simplificando, $c-1 \leq d_{i+1} \leq d_{i} \leq \dots \leq d_{2} \leq d_{1} < n, \forall i \in \mathbb {N}$. La desigualdad es estricta para los primeros valores de $i$, mientras que $c-1$ (o $c$) es menor que el anterior término de la lista. Veamos que esto sucede hasta que para un $e$ (natural, no el de $e^{\pi i}+1=0$ ), se cumple $d_{e}=c+1$, con la cual cumpliríamos nuestro objetivo, y luego tendríamos $d_{e+1}=\frac{c-1+c+1}{2}=c$ y $d_{e+i+1}=\frac{c+d_{e+i}}{2}=\frac{c+c}{2}=c, \forall i \in \mathbb {N}$, se vuelve constante (ahí hubo una breve inducción pero no la hacemos muy formal porque no es el punto central de nuestro objetivo).
Pensemos: tenemos esta lista de números enteros estrictamente decreciente en sus primeros valores y acotada por debajo en $c-1$ (y por arriba en $n$), por lo que en efecto existe ese $d_{e}=c+1$. Ah, ¿No?, ¿Es posible que el término anterior no lo sea y luego se convierta directamente en $c$, salteándose el $c+1$ y por lo tanto perdemos?. Para esto vamos a usar de subíndice $x$ porque es clave y queda bien (y me gusta así): tendríamos que el siguiente número de la lista es $c=\frac{c-1+d_{x}}{2}$ (sumamos $c-1$ porque si queremos conseguir el $c$ con el promedio de $c$ y otro número, el término anterior, ese otro número tendría que ser $c$, pero por el decrecimiento de la lista todavía no lo tenemos). De este modo, despejando $2c=c-1+d_{x} \Rightarrow d_{x}=2c-c+1=c+1$, por lo que en realidad ese término anterior era $c+1$ y simplemente quisimos hacer lío, ya habíamos cumplido con el objetivo.
Otra aclaración: dijimos que no se puede convertir directamente en $c$, salteándose el $c+1$, pero, ¿Puede ser que se convierta en $c-1$? No, por algo que ya dijimos antes, para que promediando con otro número, el término anterior, y $c-1$ obtengamos $c-1$, necesitaríamos que el término anterior sea $c-1$, pero por el decrecimiento de la lista todavía no lo tenemos.
Finalmente, completamos la inducción y probamos que teniendo $0$, $1$ y $n$ es posible escribir el resto de los números.

Otra aclaración: en la lista $d$, escribimos en el pizarrón varios números más grandes que $c+1$ y después queremos volver a escribirlos. No hay ningún problema, si queremos, podemos simular que estamos aplicando la operación pero en realidad ya tenemos el número que queremos. Repetir un número en el pizarrón no cambia nada.

Bien, con esta propiedad concluimos lo siguiente: para cada $n$, se necesitan como mínimo $2$ o $3$ números inicialmente (recordemos que el $0$ y el $n$ siempre están escritos inicialmente).

Por último, afirmo que el mínimo es $2$, si y solo si $n=2^g, g \in \mathbb {N}_{0}$.
Demostración: dividamos en dos casos:
Caso a): $n=2^g, g \in \mathbb {N}_{0}$. Escribimos el número $\frac{0+2^g}{2}=2^{g-1}$, luego el $\frac{0+2^{g-1}}{2}=2^{g-2}$ y repitiendo esto $g-3$ veces más, podemos terminar escribiendo $\frac{0+2^{g-(g-1)}}{2}=\frac{2^1}{2}=1$, por lo que conseguimos tener el $0$, el $1$ y el $n$ y por nuestra propiedad sabemos que es posible conseguir los números restantes y ganamos. Es decir que el mínimo es $2$ ($0$ y $n$).
Caso b): $n$ no es potencia de $2$, es decir que se puede representar como $n=2^h \cdot j, h \in \mathbb {N}_{0}, j \geq 3$ impar. Supongamos que el mínimo es $2$. Tenemos escritos el $0$ y el $n=2^h \cdot j$. Veamos por inducción que es imposible escribir el $1$ (y por lo tanto perdemos, absurdo, y el mínimo es $3$):
.Caso base: inicialmente tenemos $0 \equiv n=2^h \cdot j \equiv 0 (mod j)$, dos múltiplos de $j$.
.Paso inductivo: si todos los números del pizarrón, $0=jc_{0}, jc_{1}, jc_{2}, \dots ,j_{k}, 2^h \cdot j=jc_{k+1}$, son múltiplos de $j$, entonces el siguiente número es $\frac{jc_{l}+jc_{m}}{2}=j \frac {c_{l}+c_{m}}{2}$ un múltiplo de $j$ (como $j$ es impar, $2 \not \mid j$, no le saca ningún factor y queda múltiplo de $j$).
Completamos la inducción, los únicos números que podemos escribir son múltiplos de $j$. Entonces por ejemplo no podemos escribir el $1$ ($j \geq 3$), absurdo.
De este modo, en este caso sí es necesario que el mínimo sea $3$.

RTA: cuando $n$ es potencia de $2$ (no negativa), el mínimo es $2$. Cuando no lo es, el mínimo es $3 \blacksquare$

[Sandy]

Solución:

Spoiler: mostrar

Uno de los dos problemas que, si no fue mi preferido, pega en el palo

Spoiler: mostrar

Veremos que si $n$ es potencia de $2$ la respuesta es $2$, y si no lo es la respuesta es $3$.
Veremos primero el método para llegar a $2$ o $3$, dependiendo del caso.
Sea $a$ tal que $2^a\leq n<2^{a+1}$. Borraremos los números $1,2,..., n-2^a-1$ en orden ascendente como promedio de $0$ y su doble. Veamos por qué siempre podremos hacer esto:
En primer lugar, $2(n-2^a-1)=2n-2^{a+1}-2<2n-2^{a+1}<2n-n=n$, luego todos los dobles estarán en nuestro conjunto.
En segundo lugar, notemos que al momento de borrar un número $c$, tenemos sin borrar todos los mayores que $c$ y el $0$, luego $2c$ y $0$ seguirán estando.
Después de haber realizado eso, notemos que nos quedan $n-(n-2^a-1)=2^a+1$ números consecutivos. Veremos que podemos borrar todos menos $n-2^a$ y $n$.
Primero, notemos que $\frac{(x+t)+(y+t)}{2}=\frac{x+y}{2}+t$. Es decir que poder borrar $z$ con $x,y$ es equivalente a poder borrar $t+z$ con $x+t,\; y+t$. Además, $\frac{tx+ty}{2}=t\frac{x+y}{2}$. Es decir que poder borrar $z$ con $x, y$ es equivalente a poder borrar $tz$ con $tx,\; ty$. Esto nos permite desplazar y escalar un conjunto de números, manteniéndose inalterables los pasos seguidos.
Particularmente, sea $b_m$ una progresión aritmética de primer término $j$ y diferencia $d$, podemos desplazarla para que $j=0$ (restándole $j$ a todos los términos) y escalarla por un factor de $\frac{1}{d}$. Así, poder llegar de un conjunto $A$ a tener un conjunto $B$, es equivalente a poder llegar del conjunto $A\times j_1+j_2$ al conjunto $B\times j_1+j_2$. (aplicarle una operación a un conjunto implica aplicarle esa operación a todos los elementos del conjunto).
Ahora, tener $2^a+1$ números consecutivos es tener una progresión aritmética, por lo que podemos desplazarla y escalarla para que nos quede el conjunto $\{0,1,...,2^a\}$. Veremos que de este conjunto se puede llegar a $\{0,2^a\}$ por inducción en $a$.
Para $a=0$ y $a=1$ claramente es posible esto.
Supongamos que para $a=k\geq 1$ se puede. Supongamos que tenemos $\{0,1,2,...,2^{k+1}\}$. Usando los pares consecutivos de números pares podemos borrar los $2^{k}$ números impares. Ahora nos queda entonces una progresión aritmética de $2^k+1$ términos (pero con diferencia $2$), por lo que equivale a tener $\{0,1,2,...,2^k\}$, que sabemos que podemos llevar a $\{0,2^k\}$ por la hipótesis inductiva. Luego es siempre posible lograr nuestro objetivo.
Ahora, veamos cuántos números quedan después de esto.
Si $n=2^a$, $n-2^a=0$, luego el conjunto de $2^a+1$ números incluirá ya al $0$, luego al final quedarán $0$ y $n$.
Si $n$ no es potencia de $2$, $n>2^a\Longrightarrow n-2^a>0$, luego al final quedarán $0,\; n-2^a,\; n$.

Es claro por qué nunca pueden quedar más de dos números, pues para que dos números distintos promedien $q$ deben ser uno mayor que $q$ y otro menor, pero no hay ningún número menor que $0$ ni mayor que $n$, luego estos dos no podrán ser borrados.

Veamos por qué, cuando $n$ tiene algún divisor impar $2r+1>1$, no pueden quedar sólo dos números.
Notemos que dos números múltiplos de $2r+1$ promedian otro número múltiplo de $2r+1$, ya que $\frac{g_1(2r+1)+g_2(2r+1)}{2}=(2r+1)\frac{g_1+g_2}{2}$ y, al ser $2r+1$ y $2$ coprimos, debe ser $\frac{g_1+g_2}{2}\in\mathbb{N}$.
Dado que vimos que $0$ y $n$ quedarán al final, si pudiéramos borrar todos menos esos dos, al final tendremos todos múltiplos de $2r+1$. Pero si todos son múltiplos de $2r+1$, el número borrado justo antes también debe serlo (ya que es el promedio de dos números que quedan). Luego antes de borrarlo ya eran todos los números múltiplos de $2r+1$. Por inducción, vemos que en todo momento eran todos múltiplos de $2r+1$, lo cual es absurdo pues, por ejemplo, $1$ no lo es y al inicio estaba en el conjunto.

Luego, si $n$ es potencia de $2$ quedarán como mínimo $2$ números, y si no lo es quedarán como mínimo $3$ números.