Rioplatense 2017 - N1 P6

[ésta]

En la pizarra están escritos algunos números enteros positivos. Existen dos operaciones permitidas:
(1) Elegir dos números $a$ y $b$ escritos en la pizarra, borrarlos y escribir el número $a+b$.
(2) Elegir un número par $n$ escrito en la pizarra, borrarlo y escribir dos veces el número $\frac{n}{2}$.
Sea $M$ el mayor número escrito en la pizarra y sea $k$ la cantidad de números $1$ escritos en la pizarra. Demostrar que si $M \leq 2^{k+1}$ entonces es posible lograr, mediante una secuencia de operaciones permitidas, que todos los números de la pizarra sean iguales a $1$.

[Joacoini]

Spoiler: mostrar

Esta claro que si $M=1$ se cumple.
Supongamos que para $M\leq n-1$ el enunciado es correcto y sea $k=a$ donde $a$ donde es el menor número entero que cumple $n-1\leq 2^{a+1}$.
Partiendo de la suposición voy a demostrar que si $M=n$ también cumple, como para $M=n$, $a\leq k$ si hay otros números distintos de $n$ y $1$ los podemos, por la suposición, transformar en unos (notar que la suma de los números del pizarrón es invariante así que la cantidad de unos después de esto va a seguir siendo mayor o igual a $a$). Separó en problema en 3 casos.

Caso 1
$n$ es par, lo borramos y escribimos dos veces $n/2$, ahora el nuevo $M=\frac{n}{2} \leq n-1$ y $a\leq k$ lo cual hemos supuesto que cumplía el enunciado.

Caso 2
$n$ es impar y $n<2^{a+1}$, a $n$ le sumamos $1$ (ahora $a-1\leq k$) y luego lo dividimos por 2, como $n+1\leq 2^{a+1}$, ahora $M=\frac{n+1}{2}\leq \frac{2^{a+1}}{2}=2^{a-1+1}$ por la suposición esta última situación se puede transformar en todos unos.

Caso 3
$n=2^{a+1}+1$, así que $a+1\leq k$, a $n$ le sumamos $1$ (ahora $a\leq k$) y luego lo dividimos por 2, como $n+1=2^{a+1}+2$, ahora $M=\frac{n+1}{2}= \frac{2^{a+1}+2}{2}=2^{a}+1\leq 2^{a+1}$ por la suposición esta última situación se puede transformar en todos unos.