APMO 2022 P4

[Gianni De Rico]

Sean $n$ y $k$ números enteros positivos. Ceci juega al siguiente juego. Hay $n$ piedras y $k$ cajas, con las piedras numeradas de $1$ a $n$. Inicialmente, todas las piedras están en una sola caja. En cada turno, Ceci elige una caja y traslada la piedra con el número más bajo de esa caja, digamos $i$, o bien a cualquier caja vacía o bien a la caja que contiene la piedra $i+1$. Ceci gana si en algún momento del juego hay una caja que sólo contiene la piedra $n$.
Determinar todas las parejas de enteros $(n,k)$ con las que Ceci puede ganar el juego.

[Gianni De Rico]

Tengo una solución parcial, y me dicen por cucaracha que la respuesta está bien, la dejo acá por si a alguien se le ocurre cómo terminarla o para seguir pensándola después, lo que pase primero

Spoiler: mostrar

Llamamos especial a la caja en la que están inicialmente las piedras y normales a las demás cajas. Decimos que un par $(n,k)$ es ganador si Ceci puede ganar el juego con dicho par, en caso contrario decimos que el par $(n,k)$ es perdedor.

Observación 1: Si $(n,k)$ es ganador, entonces $(n,m)$ es ganador para todo $m\geq k$.
Demostración: Si Ceci tiene $m\geq k$ cajas y puede ganar con $k$ cajas, entonces usa su estrategia ganadora en las primeras $k$ cajas.

Observación 2: Si $(n,k)$ es perdedor, entonces $(n,m)$ es perdedor para todo $m\leq k$.
Demostración: Es una consecuencia inmediata de la Observación 1 (lectores entrenados reconocerán que es su contrarrecíproco). Si Ceci pudiera ganar con algún $m\leq k$, entonces podría ganar con $k$.

Observación 3: Si $(n,k)$ es ganador, entonces $(m,k)$ es ganador para todo $m\leq n$.
Demostración: Notemos que Ceci puede sacar una piedra de la primera caja únicamente cuando ya sacó todas las anteriores, de modo que si ganó con $n$ piedras y $k$ cajas, haciendo el mismo procedimiento con $m$ piedras y $k$ cajas puede dejar sola a la piedra $m$.

Observación 4: Si $(n,k)$ es perdedor, entonces $(m,k)$ es perdedor para todo $m\geq n$.
Demostración: Es una consecuencia inmediata de la Observación 3. Si $(m,k)$ fuera ganador, entonces $(n,k)$ también lo sería.

Combinando la Observación 1 y la Observación 2 vemos que lo que nos está pidiendo el problema es encontrar para cada $n$ el menor $k$ tal que $(n,k)$ es ganador. Afirmamos que dicho $k$ es $\left \lceil \log _2n\right \rceil +1$, en otras palabras, si $2^m$ es la menor potencia de $2$ que es mayor o igual que $n$, entonces el menor $k$ tal que $(n,k)$ es ganador es $m+1$.
Combinando la Observación 3 y la Observación 4 vemos que para demostrar esto nos alcanza con demostrar que para todo $m\in \mathbb{N}_0$ vale que $\left (2^m,m+1\right )$ es ganador y $\left (2^m+1,m+1\right )$ es perdedor, pues por la Observación 3 tenemos que $(n,m+1)$ es ganador para $2^{m-1}+1\leq n\leq 2^m$ y por la Observación 4 tenemos que $(n,m)$ es perdedor para $2^{m-1}+1\leq n\leq 2^m$.

Lo que viene ahora es la formalización del siguiente proceso para ver que $\left (2^m,m+1\right )$ es ganador.
La idea es ver que podemos distribuir todas las piedras salvo la más grande en las cajas normales, esto lo hacemos poniendo las primeras $2^{m-1}$ piedras en una caja, las siguientes $2^{m-2}$ en otra, las siguientes $2^{m-3}$ en otra, y así hasta poner la $2^m-1$ en una caja. Para ver que podemos hacer eso tenemos que ver que podemos pasar las primeras $2^{m-1}$ piedras a una sola caja, para eso pasamos primero las $2^{m-2}$ piedras más chicas a una caja, después las siguientes $2^{m-2}$ a otra, después distribuimos las primeras $2^{m-2}$ entre todas las cajas, y por último las vamos agregando de la más grande a la más chica en la caja con $2^{m-2}$ piedras, para eso en cada paso tenemos que separar todas las piedras de la caja y agregar la más grande (porque es la única forma que tenemos de mover las piedras "grandes") a la caja con $2^{m-2}$ piedras. Una vez que terminamos con esto nos van a quedar las $2^{m-1}$ piedras de la caja especial que todavía no tocamos (y que son las más grandes), $2^{m-1}$ piedras en una caja normal, y las demás cajas normales vacías. Entonces distribuimos todas las piedras que todavía no tocamos en las cajas vacías siguiendo la hipótesis inductiva, y con eso ganamos.

La formalización:

Spoiler: mostrar

Veamos por inducción fuerte en $m\in \mathbb{N}$ que si tenemos $m$ cajas normales y $2^m$ piedras en la caja especial entonces podemos dejar $2^{m-1}$ piedras de la caja especial en una misma caja normal y que podemos distribuir $2^t$ piedras en cada caja normal para $t\in \{0,\ldots ,m-1\}$, donde las cajas con más piedras son las que tienen las piedras con menor número (por ejemplo, para $m=3$ nos queda una caja con las piedras $1,2,3,4$, una caja con las piedras $5,6$ y una caja con la piedra $7$).
El caso base $m=1$ es claramente cierto, pues simplemente movemos una piedra de la caja especial a la caja normal.
Supongamos como hipótesis inductiva que vale para todos los naturales menores o iguales a $m$. Veamos que vale para $m+1$.
Por hipótesis inductiva podemos poner las primeras $2^{m-1}$ piedras en una caja normal usando $m$ cajas normales. Tenemos entonces la caja especial con $2^{m+1}-2^{m-1}$ piedras, una caja normal con las primeras $2^{m-1}$ piedras y $m$ cajas normales vacías. Usando nuevamente la hipótesis inductiva, podemos poner las siguientes $2^{m-1}$ piedras en otra caja normal usando $m$ cajas normales. Tenemos entonces la caja especial con $2^{m+1}-2^{m-1}-2^{m-1}=2^m$ piedras, una caja normal con las primeras $2^{m-1}$ piedras, una caja normal con las siguientes $2^{m-1}$ piedras y $m-1$ cajas normales vacías.
Ignoremos ahora la caja especial y la caja normal con las $2^{m-1}$ piedras más grandes, a la que llamaremos la caja pesada, y tratemos a la caja normal con las $2^{m-1}$ piedras más chicas como la caja especial. Usando la hipótesis inductiva, podemos distribuir $2^t$ piedras en cada caja normal para $t\in \{0,\ldots ,m-2\}$. Esto nos deja la piedra $2^{m-1}$ sola. Entonces vamos a hacer lo siguiente: Tomamos la piedra $2^{m-1}$ y la pasamos a la caja pesada, tomamos la piedra $2^{m-1}-1$ (que está sola) y la pasamos a la caja pesada, esto nos deja $2$ cajas vacías y la caja con menos piedras (y las piedras más grandes) tiene $2=2^{2-1}$ piedras, entonces las podemos distribuir como recién y volver a pasar todas a la más pesada, lo que nos deja $3$ cajas vacías y la caja con menos piedras (y las piedras más grandes) tiene $4=2^{3-1}$ piedras. Bueno, el chiste es que podemos seguir haciendo lo mismo, pero yo no tengo ganas de escribir otra inducción más, así que queda como ejercicio para el lector (igual es fácil).
Habiendo hecho esto, nos quedan la caja especial con $2^m$ piedras, una caja normal con $2^m$ piedras y $m$ cajas normales vacías. Entonces ganamos por hipótesis inductiva, pues distribuimos las piedras, lo que nos deja a la piedra más grande sola, y listo.

Con esto demostramos que $\left (2^m,m+1\right )$ es ganador.

[Fran5]

Acá está el paso clave... solo que lo demostraste un poco raro...

Spoiler: mostrar

Observación 3: Si $(n,k)$ es ganador, entonces $(m,k)$ es ganador para todo $m\leq n$.
Demostración: Notemos que Ceci puede sacar una piedra de la primera caja únicamente cuando ya sacó todas las anteriores, de modo que si ganó con $n$ piedras y $k$ cajas, haciendo el mismo procedimiento con $m$ piedras y $k$ cajas puede dejar sola a la piedra $m$.

En realidad lo que pasa es que

Spoiler: mostrar

Si $(n,k)$ es ganador, y $m \leq n$, entonces lo que pasó es que, para dejar solita a la bolita $n$ en la primer caja, necesariamente tuvimos que retirar las bolitas $1 \leq m \leq n-1$ de la primer caja. Como la bolita $m+1$ sigue estando en la primer caja, entonces la bolita $m$ tuvo que haberse movido a una caja vacía. Ignorando las bolitas mayores a $m$, tenemos que $(m,k)$ es ganador.

OBS: más fuerte aún y lo voy a usar despues, vemos que si $(n,k)$ es ganador entonces $(m,k-1)$ es ganador para todo $m<n$

Luego lo podemos terminar de la siguiente forma

Spoiler: mostrar

Basta ver por las observaciones que, para cada $k$, el par $(2^k,k+1)$ es ganador y el par $(2^k+1,k+1)$ es perdedor. Luego $(n,k)$ es ganador si y sólo si $1 \leq n \leq 2^{k-1}$.

Para $n=2^k$ y $k+1$ cajas, ya se mostró por inducción fuerte cómo se puede resolver el problema.

Supongamos que existe algún par $(n,k+1)$ ganador con $n \geq 2^{k}+1$. Luego obtendríamos que el par $(2^{k}+1,k+1)$ es ganador por la observación $3$. Elijamos el menor número natural $k$ tal que $(2^{k}+1,k+1)$ es ganador. Claramente $k+1>2$ pues con $2$ cajas no podemos despejar tres bolitas.

En algún momento, tuvimos que haber movido la bolita $2^{k-1}+1$. Hasta ese momento sólo movimos las bolitas $1 \leq j \leq 2^{k-1}$. Más aún, la bolita $2^{k-1}+1$ se tuvo que haber movido a una caja vacía, WLOG, la última caja (la $k+1$)
Ignorando la última caja y las bolitas $2^{k-1}+2 \leq j \leq 2^{k}+1$, tuvimos una situación en la cual había $2^{k-1}+1$ bolitas y $k$ cajas, y nos quedó solita la bolita $2^{k-1}+1$ en la primer caja, de donde $(2^{k-1}+1,k)$ resultaría ganador contradiciendo la elección de $k+1$ como el menor con esas propiedades.

Luego no puede haber par ganador de la forma $(2^k+1,k+1)$ lo que completa la solución

[ésta]

Cuidado

Spoiler: mostrar

Ignorando la última caja y las bolitas $2^{k−1}+2≤j≤2^k+1$, tuvimos una situación en la cual había $2^{k−1}+1$ bolitas y $k$ cajas, y nos quedó solita la bolita $2^{k−1}+1$ en la primer caja, de donde $(2^{k−1}+1,k)$ resultaría ganador contradiciendo la elección de $k+1$ como el menor con esas propiedades.

No se puede ignorar la última caja así nomas porque si bien tiene que estar vacía al momento de pasar la bolita $2^{k-1}+1$, pudo haber sido usada en pasos anteriores para hacer lugar para otras bolitas y luego vaciada. De hecho, tu argumento no es fuerte en la cota $2^k+1$. Es decir, el mismo argumento se puede enunciar para $2^k$ bolitas pero con $2^k$ bolitas se puede.