Alice y Bob están jugando una variante del juego de Nim. Hay pilas que consisten en monedas respectivamente. En un movimiento, un jugador puede quitar un número cuadrado de monedas de cualquier pila; por ejemplo, uno puede quitar 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 formado por todas las particiones posibles de un número en cuadrados. Por ejemplo,
Ahora, si solo hay una pila, entonces la pila puede aproximarse a cero en algún orden, digamos , entonces por definición de . Digamos el número total de números en un camino será . En un juego de una pila, Alicia gana si es impar, de lo contrario, Bob gana.
Del mismo modo, en un -juego de pila, Alicia gana si la suma de los valores de 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 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 . ¿Puede alguien ayudarme?
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 a un poco ).
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 , respectivamente.
Mirando la secuencia OEIS, encontramos que los números correspondientes son , respectivamente.
Luego calculamos el xor de los tres nimbers, que es .
Esto significa que el juego original es equivalente a un montón de nim, por lo tanto, Alice pierde (ya que ella mueve primero y no hay movimiento legal).
Por otro lado, si las tres pilas son , entonces los nimbers son y el xor de ellos es . Esto significa que Alicia gana.
En general, Alice pierde si y solo si el xor de todos los nimbers es igual a .
Qué pasa
ultraleyenda5385