Dos jugadores $A$ y $B$ compiten en el siguiente juego. Se coloca una cierta cantidad $N_0\geq 2$ de piedras. Cada jugador alternadamente, comenzando por $A$, retira un cierto número de piedras en su turno, siendo este número mayor o igual que $1$ y menor o igual que la mitad de las piedras que quedan en el montón. Pierde el primer jugador que, en su turno, encuentra una única piedra en el montón. Justificar para qué valores de $N_0$ existe una estrategia ganadora para cada jugador. Si $N_0$ recorre todos los valores entre $2$ y $2^{2021}$ y ambos jugadores siguen su estrategia ganadora, hallar en cuántos casos ganaría cada uno.
Solución. Veamos en primer lugar que, si uno de los jugadores, llamémoslo $X$, tras su turno, le deja al otro $2^k-1$ piedras, entonces puede jugar inteligentemente para ganar independientemente de los movimientos del otro. Lo probaremos por inducción sobre $k$. Si $k=0$, está claro que $X$ gana porque le deja sólo una piedra al otro. Supuesto que si $X$ le deja al otro $2^k-1$ piedras, entonces tiene estrategia ganadora, supongamos que consigue dejarle $2^{k+1}-1$ piedras. En su turno, el otro jugador quitará una cantidad $1\leq m\leq \lfloor\frac{2^{k+1}-1}{2}\rfloor=2^k-1$ piedras, luego $X$ solo debe quitar $2^k-m$ piedras para dejar el montón en $2^k-1$ y entonces usar la hipótesis de inducción. Hemos de comprobar, no obstante, que este movimiento de $X$ está permitido, es decir, que $1\leq 2^k-m\leq\frac{2^{k+1}-1-m}{2}$. En efecto, se cumple que $1\leq 2^k-m$ porque $m\leq 2^k-1$ y se cumple que $2^k-m\leq\frac{2^{k+1}-1-m}{2}$ porque $m\geq 1$.
Usando esta información, si escribimos $N_0=2^k+a$ para cierto enteros $k\geq 1$ y $0\leq a\lt 2^k$, el jugador $A$ puede quitar entre $1$ y $2^{k-1}+\lfloor\frac{a}{2}\rfloor$ piedras. Como hemos supuesto que $a\lt 2^k$, este último número es mayor que $a$ salvo que $a=2^k-1$. Por lo tanto, $A$ puede conseguir en su primer movimiento que queden $2^k-1$ piedras y gana de esa forma, salvo que $a=2^k-1$. Por el contrario, si $a=2^k-1$, en su primer movimiento $A$ necesariamente deja un número de piedras $N_1=2^k+b$ con $0\leq b\lt 2^k-1$ y $B$ puede aplicar el mismo razonamiento para dejar $2^k-1$ piedras tras su primer movimiento y así ganar.
Así, tenemos que contar cuántos números entre $2$ y $2^{2021}$ son de la forma $2^k+2^k-1=2^{k+1}-1$ con $k\geq 1$. Esto equivale a contar cuántas potencias de $2$ hay entre $3=2^1+1$ y $2^{2021}+1$ y la respuesta es obviamente $2020$. Concluimos así que $A$ gana en $2^{2021}-2020$ casos y $B$ gana en los otros $2020$ casos.
