Juego: dos pilas de monedas y reducción por divisor del número de monedas en la pila

Question

Jugador $A$ y $B$ jugar a un juego: Hay dos pilas de monedas, la primera tiene $a=12$ monedas, segundo - tiene $b=8$ monedas. Cada jugador elige una pila y retira $d$ monedas, si se elige la primera pila $d|a$ Si no es así $d|b.$ El jugador gana si el otro no puede moverse. ¿Qué jugador tiene una estrategia ganadora?

Cómo cambiar la respuesta si $a=20,b=28$ ?

Conozco la respuesta por ensayos si $a=5,b=3$ - $B$ tiene una estrategia ganadora: este jugador toma una moneda de esta pila, que fue elegida por $A$ en el último movimiento, si es posible. Si no es posible, significa que $A$ obtener la última moneda de la pila.

Tengo problemas para ver un patrón general. Pensé que en la situación que $a=12,b=8$ $B$ no se obtiene una moneda, sino $gcd(12,8)=4$ monedas por analogía con la situación descrita anteriormente; no veo por el momento ninguna razón.

Answer 1

Pude encontrar la solución, aunque no puedo explicar cómo a menos que estés familiarizado con la teoría de juegos combinatoria.

Una posición $(a,b)$ es una victoria para el primer o segundo jugador. Si exactamente uno de $a$ o $b$ es cero, entonces la posición es una victoria del primer jugador, y la jugada ganadora consiste en reducir la pila no nula a cero.

En caso contrario, deja que $v(a)$ sea la mayor potencia de dos que se divide en $a$ . Por ejemplo, $v(20)=4, v(120)=8, v(16)=16, v(\text{any odd number})=1$ .

Theoerm: Si $a,b>0$ el juego $(a,b)$ es una victoria para el primer jugador si y sólo $v(a)\neq v(b)$ .
Si $v(a)>v(b)$ entonces una estrategia ganadora es disminuir $a$ por $v(b)$ .
Si $v(a)<v(b)$ entonces una estrategia ganadora es disminuir $b$ por $v(a)$ .

Cuando $(a,b)=(12,8)$ entonces $v(a)=4$ y $v(b)=8$ , por lo que esta posición es una victoria para el primer jugador. Una jugada ganadora es disminuir $8$ por $4$ , lo que da lugar a la posición $(8,8)$ .

Cuando $(a,b)=(20,28)$ entonces $v(a)=4$ y $v(b)=4$ , por lo que esta posición es una pérdida para el primer jugador. Esto significa que cada movimiento del primer jugador tiene una respuesta ganadora: por ejemplo, si el primer jugador elimina $4$ de la primera pila, dejando $(16,28)$ entonces el segundo jugador respondería eliminando $v(28)=4$ de la $16$ pila, dejando $(12,28)$ .

Para demostrar el teorema, basta con demostrar dos cosas. Llamar a una posición igualado si $v(a)=v(b)$ .

• Si una posición no está igualada, la realización del movimiento descrito anteriormente la iguala.

• Si una posición está igualada, cualquier movimiento la dejará sin igualar.

Dejo estas pruebas al lector.

---

En cuanto a cómo encontré esta estrategia; el juego de dos pilas es el suma de dos juegos de una pila. Se puede calcular el Valores de Grundy de un juego de una pila recursivamente haciendo una tabla, y para cada entrada dejando que el valor sea el mex de los valores de ese número menos sus divisores. Después de hacer eso vi un patrón y lo probé. Ahora no sé cómo habría visto el patrón sin estar familiarizado con el en cursiva conceptos.