Ana y Beto juegan, por turnos, al siguiente juego. Inicialmente hay una pila con $n$ piedras. Cada jugador, en su turno, debe retirar un número de piedras mayor que $1$, que sea divisor del número total de piedras en la pila en el momento que le toca el turno, pero debe dejar por lo menos una piedra en la pila. El primer jugador que no puede realizar su jugada, pierde el juego. Ana juega en el primer turno. Hallar todos los enteros positivos $n$ para los que Ana puede desarrollar una estrategia que le asegure la victoria.
Veremos que Ana tiene una estrategia ganadora si y sólo si $n$ es par.
Lo probaremos por inducción fuerte sobre $n$.
Como casos base tenemos $n=2$ y $n=3$. Para $n=2$, Ana saca una piedra, por lo que Beto recibe una pila de una piedra, entonces no puede jugar y pierde. Para $n=3$, como los únicos divisores de $3$ son $1$ y $3$, y Ana no puede sacar $3$ piedras (porque dejaría vacía la pila), debe sacar una piedra, entonces Beto recibe una pila de dos piedras y gana haciendo lo mismo que Ana en el caso anterior.
Supongamos como hipótesis inductiva que para todos los $n\leqslant 2k$, Ana tiene una estrategia ganadora si y sólo si $n$ es par. Veamos que esto vale para $2k+1$ y $2k+2$.
Como $2k+1$ es impar, no puede tener ningún divisor par, luego, todos sus divisores son impares, por lo tanto Ana saca $2x+1$ piedras de la pila (con $x\in \mathbb{N},x<k$), por lo que Beto recibe una pila con $2k+1-(2x+1)=2k-2x=2(k-x)$ piedras, que es un número par. Como Ana tiene una estrategia ganadora para todos los números pares, Beto puede aplicar esa estrategia y ganar. Por lo tanto, para $n=2k+1$ Ana no tiene una estrategia ganadora.
Para $n=2k+2$, Ana saca una piedra, entonces Beto recibe una pila de $2k+1$ piedras, y ya vimos que eso significa que Beto pierde, entonces Ana tiene una estrategia ganadora para $n=2k+2$. Esto completa la inducción.
Veremos que Ana tiene una estrategia ganadora si y sólo si $n$ es par.
Lo probaremos por inducción fuerte sobre $n$.
Como casos base tenemos $n=2$ y $n=3$. Para $n=2$, Ana saca una piedra, por lo que Beto recibe una pila de una piedra, entonces no puede jugar y pierde. Para $n=3$, como los únicos divisores de $3$ son $1$ y $3$, y Ana no puede sacar $3$ piedras (porque dejaría vacía la pila), debe sacar una piedra, entonces Beto recibe una pila de dos piedras y gana haciendo lo mismo que Ana en el caso anterior.
Supongamos como hipótesis inductiva que para todos los $n\leqslant 2k$, Ana tiene una estrategia ganadora si y sólo si $n$ es par. Veamos que esto vale para $2k+1$ y $2k+2$.
Como $2k+1$ es impar, no puede tener ningún divisor par, luego, todos sus divisores son impares, por lo tanto Ana saca $2x+1$ piedras de la pila (con $x\in \mathbb{N},x<k$), por lo que Beto recibe una pila con $2k+1-(2x+1)=2k-2x=2(k-x)$ piedras, que es un número par. Como Ana tiene una estrategia ganadora para todos los números pares, Beto puede aplicar esa estrategia y ganar. Por lo tanto, para $n=2k+1$ Ana no tiene una estrategia ganadora.
Para $n=2k+2$, Ana saca una piedra, entonces Beto recibe una pila de $2k+1$ piedras, y ya vimos que eso significa que Beto pierde, entonces Ana tiene una estrategia ganadora para $n=2k+2$. Esto completa la inducción.
Decimos que una posición (cantidad de fichas) es ganadora o perdedora si el primero que juega con esa cantidad gana o pierde, respectivamente.
Digo que $n$ es ganador si y sólo si $n$ es par pero no es una potencia impar de $2$. Lo demostraremos con inducción:
Es obvio que $n=1$ es perdedor. Ahora, supongamos que para todo $k<n$ se cumple lo dicho. Tenemos varios casos:
Caso i: $n$ es par pero no potencia de dos.
Claramente, $n$ tiene un divisor impar $d$. Luego, si se sacan $d$, quedan $n-d\equiv 1\mod 2$. Por hipótesis, esto es una posición perdedora, por lo que $n$ es ganador.
Caso ii: $n$ es potencia par de $2$.
Es claro que $2^{k-1}$ divide a $2^k$. Sacando eso, obtenemos $2^{k-1}$ que es perdedora (por ser potencia impar de $2$). Luego $n=2^k$ es ganadora.
Caso iii: $n$ es potencia impar de $2$.
Si $n=2^k$, es obvio que Ana deberá sacar $2^m$ con $1\leq m<k$. Luego, se obtendrá $2^k-2^m=2^m(2^{k-m}-1)$ que es par, pero no potencia impar de $2$ (si lo fuera, digamos que es $2^l$, $2^{k-m}=2\Longrightarrow l=m=k-1$, que es par). Luego, Ana pierde no importa lo que haga, o sea, $n$ es perdedor.
Caso iv: $n$ es impar.
Para $n$ primo, es obvio que Ana pierde. Desde ahora, $n$ es compuesto.
Supongamos que Ana toma un divisor $d_1$. Sea $d_2$ tal que $d_1d_2=n$. Es claro que $d_1$, $d_2$ son impares. Beto recibe $d_1d_2-d_1=d_1(d_2-1)$ que es par pero no potencia de $2$ (ya que $d_1>1$ es impar). Luego, Ana siempre pierde, o $n$ es perdedor.
Ahora, aplicando inducción fuerte, llegamos al resultado deseado.
Veremos que Ana tiene una estrategia ganadora si y sólo si $n$ es par.
Lo probaremos por inducción fuerte sobre $n$.
Como casos base tenemos $n=2$ y $n=3$. Para $n=2$, Ana saca una piedra, por lo que Beto recibe una pila de una piedra, entonces no puede jugar y pierde. Para $n=3$, como los únicos divisores de $3$ son $1$ y $3$, y Ana no puede sacar $3$ piedras (porque dejaría vacía la pila), debe sacar una piedra, entonces Beto recibe una pila de dos piedras y gana haciendo lo mismo que Ana en el caso anterior.
Supongamos como hipótesis inductiva que para todos los $n\leqslant 2k$, Ana tiene una estrategia ganadora si y sólo si $n$ es par. Veamos que esto vale para $2k+1$ y $2k+2$.
Como $2k+1$ es impar, no puede tener ningún divisor par, luego, todos sus divisores son impares, por lo tanto Ana saca $2x+1$ piedras de la pila (con $x\in \mathbb{N},x<k$), por lo que Beto recibe una pila con $2k+1-(2x+1)=2k-2x=2(k-x)$ piedras, que es un número par. Como Ana tiene una estrategia ganadora para todos los números pares, Beto puede aplicar esa estrategia y ganar. Por lo tanto, para $n=2k+1$ Ana no tiene una estrategia ganadora.
Para $n=2k+2$, Ana saca una piedra, entonces Beto recibe una pila de $2k+1$ piedras, y ya vimos que eso significa que Beto pierde, entonces Ana tiene una estrategia ganadora para $n=2k+2$. Esto completa la inducción.
Se me pasó jajajaja. Teniendo eso en cuenta, mi solución quedaría idéntica a la de Bruno.
Llamo $p_j$ a la piedra en la j-ésima posición, tal que la piedra al fondo de la pila es $p_1$ y la de arriba del todo $p_n$. Además, llamo ganadoras o perdedoras a las piedras que garantizan victoria o derrota respectivamente a quien empiece su turno en ellas.
Lema 1: Sea $p_x$ perdedora. Luego, como de $p_{x+1}$ se puede llegar a $p_x$ sacando $1$ piedra, $p_{x+1}$ es ganadora.
Lema 2: Sea $p_i$ una piedra con $i$ impar y sean todas las piedras $p_{i-1}$, $p_{i-3}$, $p_{i-5}$ ... $p_2$ ganadoras. Luego, como todos los divisores de $i$ son impares, todo movimiento posible deja al rival en posición ganadora y $p_i$ es perdedora.
Por último, vemos que $p_1$ pierde y $p_2$ gana. De ahí, por los lemas 1 y 2, todas las piedras en posiciones impares son perdedoras y todas las piedras en posiciones pares son ganadoras (véase que si todas las piedras $p_{i-1}$, $p_{i-3}$, $p_{i-5}$ ... $p_2$ son ganadoras, y $p_i$ es perdedora, entonces $p_{i+1}$ es también ganadora y $p_{i+2}$ es también perdedora). $n$ tiene que ser par.
Creo que llegué básicamente a la solución de @BrunZo, pero con inducción débil.
Llamo $p_j$ a la piedra en la j-ésima posición, tal que la piedra al fondo de la pila es $p_1$ y la de arriba del todo $p_{n}$. Además, llamo ganadoras o perdedoras a las piedras que garantizan victoria o derrota respectivamente a quien empiece su turno en ellas.
Primero veamos que los primos pierden porque sacar los divisores implica un movimiento ilegal (sacar $1$ o sacar todas).
Luego, $p_2$, $p_3$, $p_5$ y $p_7$ son perdedoras porque son posiciones de números primos. De ahí, se sigue que $p_4$ y $p_6$ son ganadoras y $8$ es perdedora porque $8-4=4$ y $8-2=6$ son ambas ganadoras.
Asumamos que hay una piedra $p_\gamma$ tal que entre $p_2$ y $p_\gamma$ pierden todas las impares y las potencias impares de $2$, y gana el resto.
Si $p_\gamma=p_{2^\alpha}$ es potencia impar de $2$, es perdedora: Todos sus divisores son pares, entonces restarle cualquiera a $2^\alpha$ resulta en par. El par más chico resulta $2^{\alpha-1}$, que es potencia par de $2$ y todas las pares entre medio, contándola, son ganadoras.
Ahora, si $p_\gamma$ es $p_i$ con $i$ impar no primo, también es perdedora: Todos los divisores de $i$ son impares $f$ y su diferencia par, o sea que, o $i-f=2^\alpha$ para algún $\alpha$ impar o $i-f=2\times \beta$ para algún beta entero que no es potencia par de $2$. Veamos que el primer caso es imposible: $2^\alpha+f\equiv i \pmod{f}\implies2^\alpha\equiv 0\pmod{f}$, pero vimos que $f$ era impar, absurdo. Entonces, todas las diferencias entre $i$ y sus divisores darán par ganadora.
Por último, si $p_\gamma$ es $p_q$ con $q$ par no potencia impar de $2$, es ganadora: Dividir a $q$ la mayor cantidad de veces posible sin que deje de ser entero resulta en un divisor impar perdedora o en $1$, en cuyo caso $\frac{q}{2}$ es una potencia impar de $2$ perdedora.
Ya vimos que se cumple para $p_\gamma$ hasta $8$ (con lógica booleana hacía falta hasta $4$, pero a nadie le gustaría eso) , queda demostrado de ahí para arriba. Las posiciones ganadoras de $n$ son los números pares exceptuando a las potencias impares de $2$.
En realidad, usaste inducción fuerte, que es suponer que se cumple para todos los anteriores ($k\leqslant n$). Inducción común es suponer únicamente que se cumple para $k=n-1$.
De todos modos, te faltaría explicar por qué funcionan un par de los casos. Por ejemplo, mostrar por qué restando un divisor de una potencia impar de $2$, no podés llegar a una potencia impar de $2$. O mostrar cuál es el paso que tiene que hacer Ana para llegar a una posición perdedora cuando tiene una potencia par de $2$.