Pregunta de teoría de juegos sobre una variante de Nim

Alice y Bob están jugando una variante del juego de Nim. Hay norte pilas que consisten en a , b , C , monedas respectivamente. En un movimiento, un jugador puede quitar un número cuadrado de monedas de cualquier pila; por ejemplo, uno puede quitar 1 , 4 , 9 , monedas de cualquiera de las pilas en un solo movimiento. No se permiten movimientos vacíos. El jugador que no puede moverse pierde. Supongamos que Alice va primero. Determine la condición de que Alice gane, así como elabore una estrategia ganadora para él. Suponga que ambos jugadores juegan de manera óptima.

Aquí están mis esfuerzos:

Definir un conjunto GRAMO norte formado por todas las particiones posibles de un número norte en cuadrados. Por ejemplo,

GRAMO 6 = { 1 + 1 + 1 + 1 + 1 + 1 ,   4 + 1 + 1 }
Ahora, tenga en cuenta que si el número total de movimientos (hasta que todas las pilas se conviertan en cero) es impar, Alicia gana; si es impar, Bob gana.

Ahora, si solo hay una pila, entonces la pila puede aproximarse a cero en algún orden, digamos PAG , entonces PAG GRAMO por definición de GRAMO . Digamos el número total de números en un camino PAG será norte ( PAG ) . En un juego de una pila, Alicia gana si norte ( PAG ) es impar, de lo contrario, Bob gana.

Del mismo modo, en un norte -juego de pila, Alicia gana si la suma de los valores de norte ( PAG ) porque cada pila es impar, de lo contrario, Bob gana.

Ahora, en un juego de una pila, la estrategia de Alicia debería ser elegir ese PAG GRAMO que tiene los números más grandes, porque si elige números más pequeños, Bob puede romper su camino.

Pero soy incapaz de encontrar una estrategia para él donde norte > 1 . ¿Puede alguien ayudarme?

Solo necesitas averiguar el número de un norte -pila de monedas para cada uno norte , que es el número mínimo excluido de sus subjuegos. Haz esto durante los primeros norte y tratar de encontrar un patrón. Véase el teorema de Sprague-Grundy .
Leí esa página y llegué a saber muchas cosas. Pero, ¿podría proporcionar una solución o un procedimiento de trabajo, al menos? (Por cierto, ¿mis esfuerzos fueron legítimos?)

Respuestas (1)

Calculé los nimbers y busqué en OEIS.

El resultado es esta secuencia y un enlace útil en esa página es este documento que brinda un algoritmo rápido (que es una mejora del ingenuo O ( norte 3 / 2 ) a un poco O ( norte 1 + ϵ ) ).

El documento es bastante reciente (de 2018), lo que probablemente significa que no se conoce una forma mejor de calcular los nimbers.


Ejemplos:

Digamos que tenemos tres montones, de tamaños 37 , 51 , 87 , respectivamente.

Mirando la secuencia OEIS, encontramos que los números correspondientes son 3 , 5 , 6 , respectivamente.

Luego calculamos el xor de los tres nimbers, que es 0 .

Esto significa que el juego original es equivalente a un montón de 0 nim, por lo tanto, Alice pierde (ya que ella mueve primero y no hay movimiento legal).

Por otro lado, si las tres pilas son 37 , 51 , 83 , entonces los nimbers son 3 , 5 , 4 y el xor de ellos es 2 . Esto significa que Alicia gana.

En general, Alice pierde si y solo si el xor de todos los nimbers es igual a 0 .

Lo siento, pero no entiendo cómo usar los valores nim aquí.
Agregué ejemplos.
Oh, entonces entiendo que la suma de todos norte ( PAG ) 's es equivalente a la suma mínima del tamaño de las pilas, que si es cero, hace que Alicia pierda, de lo contrario, él gana. Por cierto, ¿hay alguna prueba de esto? Estudié la prueba de la estrategia normal de Nim, pero no pude entenderla.
¿Y hay alguna forma de obtener el valor de Nim? ¿O tenemos que mirar siempre la secuencia OEIS?
Creo que la prueba está en algún lugar de la página wiki anterior sobre el teorema de Sprague-Grundy. No es difícil calcular los nimbers: echa un vistazo a esto y verás que se calculan recursivamente usando el mex en los nimbers de los subjuegos. Consulte también este pdf que explica las cosas en detalle y tiene algunos juegos más interesantes para que los resuelva.
Gracias por ese documento, después de leerlo por completo, entendí cómo obtener el valor nim de un número. Para el juego de múltiples pilas, calcule su nim-sum; si es cero, Alicia pierde; de lo contrario gana. Muchas gracias por tu gran ayuda.
Y ahora estoy sintiendo lo que más ama un matemático: ¡resolver un problema por el que te has rascado la cabeza durante horas!
Eso es genial (: Los juegos imparciales son de hecho un tema muy interesante.
Jaja, dice MSE, estamos comentando demasiado xD