Vamos a jugar un juego de NIM, pero con una captura!
Tenemos exactamente tres pilas de piedras con tamaños $a$ , $b$ y $c$ todos los cuales son diferentes.
Nos movemos por turnos. En cada movimiento, podemos seleccionar un montón y quitar cualquier número de piedras de él. Pero hay una restricción: En ningún momento durante el juego podemos tener dos montones igualmente altos de un tamaño distinto a cero. El jugador que no puede hacer un movimiento pierde.
- el juego $(1, 3, 5)$ puede transformarse en $(0, 3, 5)$ , $(1, 2, 5)$ , $(1, 0, 5)$ , $(1, 3, 4)$ , $(1, 3, 2)$ o $(1, 3, 0)$ en un solo movimiento
- $(0, 1, 2)$ puede transformarse en $(0, 0, 2)$ o $(0, 1, 0)$
- el juego $(0, 0, 0)$ es una pérdida inmediata
Resulta que conozco una forma de calcular el resultado de tal juego: A menos que $a = b = c = 0$ el primer jugador pierde exactamente si $(a+1) \oplus (b+1) \oplus (c+1) = 0$ . $(0,0,0)$ es una pérdida también. Creo que se puede probar a través de la inducción en $a + b + c$ .
Lo que no sé es cómo se obtendría ese resultado. He estado perplejo durante bastante tiempo y he descubierto una fórmula para el caso con dos montones, pero no he podido generalizarla. Entonces busqué la solución. ¿Cómo abordaría este problema para tener una intuición de cuáles son las posiciones ganadoras o perdedoras? O mejor aún, ¿hay algún método general que a menudo funciona para este tipo de juegos?
Conozco el teorema de Sprague-Grundy y las posiciones de P y N en los juegos generales de los DAG, así que puedo usar la "fuerza bruta" para resolver el problema, pero desafortunadamente los números eran demasiado grandes para resolver el problema de esa manera y los resultados para los pequeños $a,b,c$ no me ayudó realmente a derivar la fórmula. Una observación importante que puedo sacar de esto en retrospectiva, sin embargo, es que el valor $(a+1) \oplus (b+1) \oplus (c+1)$ no parece ser el número grundy del juego, sólo que resultan ser cero para las mismas asignaciones de $a$ , $b$ y $c$ .
La fuente del problema es la Concurso de programación Andrew Stankevich 22 tarea D.
ACTUALIZACIÓN: Para el caso de los dos montones, exactamente las posiciones $(2k, 2k - 1)$ son las pérdidas. Podemos llegar desde cualquier otra posición a una de estas o a $(0, 0)$ pero no podemos pasar de uno de estos a otro de estos. El caso base es que $(1, 2)$ es una pérdida y $(0, a)$ es una victoria para $a > 0$ .
