¿Cómo puedo saber si una pila en "Grundy's game" tiene una estrategia ganadora?

Question

¿Cómo puedo saber si una pila en "Grundy's game" tiene una estrategia ganadora?

Matemáticas
Matemáticas discretas
combinatoria-teoria-de-juegos

CS1

Supongamos que estoy jugando el juego de Grundy y tengo un montón de $n$ monedas Quiero saber si tengo una estrategia ganadora (no importa cuál sea). ¿Cómo puedo saber si hay?

Entiendo la transformación a Nim heap, pero no entiendo cómo puede decirme si hay una estrategia ganadora o no:
por ejemplo: Wikipedia dice que la pila de 18 es igual a Nim heap en tamaño 4, pero si tengo una apilar en Nim, no importa cuál sea el tamaño, puedo ganar en el primer movimiento.

Entonces mi pregunta es: para una pila de tamaño $n$ en el juego de Grundy, ¿cómo puedo saber si hay una estrategia ganadora o no? (para cualquier tamaño de pila) y si alguien puede explicarme la idea de transformarlo en un montón de Nim , será genial (como dije, no entiendo la idea de transformar, porque la pila de cualquier tamaño en Nim tiene una estrategia ganadora ).

¡Gracias!

Respuestas (1)

¿Cómo puedo saber si una pila en "Grundy's game" tiene una estrategia ganadora?

usuario694818 · Answer 1

usuario694818

Es útil saber qué significa decir que un juego de Grundy con 18 fichas es equivalente a un montón de Nim de tamaño 4. Imagina que tienes dos mesas, una jugando el juego de Grundy con una sola pila de 18 fichas y otra jugando Nim con un montón de fichas. Pila única de 4 fichas. Un jugador hace un movimiento legal en uno de los juegos, y luego el otro jugador hace un movimiento en el mismo juego o en el otro juego, y así sucesivamente. (Esa es la combinación en la teoría de juegos combinatorios). Dado que esos dos juegos son equivalentes, podemos concluir que el segundo jugador siempre podrá ganar haciendo un movimiento de equilibrio en el juego que el primer jugador no eligió para su movimiento.

Entonces, al igual que Nim, ganas en el juego de Grundy si la suma mínima de los números de todas las pilas no es igual a 0, y ganas haciendo un movimiento que deja la suma mínima igual a 0. Aquí está la lista de valores nim de pilas individuales (del wiki):

Podemos ver que 3 y 15 tienen un valor mínimo de 1. Entonces, si dividimos la pila de 18 en 3 y 15, la suma mínima que le queda a nuestro oponente es $1+1=0$ , por lo que perderán si mantenemos un juego óptimo.

CS1

¡Gracias por su respuesta! Así que si te entiendo bien: 1. a

18

$18$ hay una estrategia ganadora porque

n (18) > 0

$n(18)>0$ , ¿bien? 2. si tengo dos montones:

4, 6

$4,6$ , entonces

n (4) + n (6) = 0 + 1 = 1 > 0

$n(4)+n(6)=0+1=1>0$ Entonces, ¿tengo una estrategia ganadora? 3. ¿Es la adición como la adición de montones de Nim? ¡Gracias!

usuario694818

@ CS1 Así es. Para obtener puntos de bonificación, puede ver en la tabla que los movimientos ganadores de 4 y 6 serían dividir el 4 en 3 y 1 o dividir el 6 en 4 y 2.

CS1

Gracias, así que si tengo un montón de

20

$20$ o

7

$7$ ¿No hay una estrategia ganadora?

usuario694818

@CS1 No si tu oponente juega de manera óptima. Pero el hecho de que tu oponente tenga una estrategia ganadora no significa que sepa cuál es. Así que podrías dividir 20 en 17 y 3 y esperar lo mejor.

CS1

Gracias por la aclaración. Mi pregunta (en realidad es la original): hay una manera de saber si se acumula con

n

$n$ ¿ Las monedas no tienen una estrategia ganadora? (como escribió en el último párrafo en su respuesta, pero esto fue alrededor de 3 y 15).

Marcas.

@CS1, hay un tamaño de pila Nim en el que el siguiente jugador no tiene una estrategia ganadora: tamaño

0

$0$ . Cuando Matthew Daly dijo "usted gana... si la suma mínima... no es igual a 0", eso es un "si y sólo si": no tiene una estrategia ganadora cuando la suma mínima es igual . a

0

$0$ .

CS1

@Marcas. gracias por su respuesta, pero estoy preguntando por una pila de un tamaño que es más grande que

0

$0$ por supuesto :)

Marcas.

@ CS1 Estoy un poco confundido ahora: si su pregunta ahora está completamente respondida (ya que aceptó la respuesta de Matthew Daly), ¡genial! Si no, no estoy seguro de cuál es su pregunta restante, y podría valer la pena hacer una nueva pregunta en el sitio. Si está preguntando: "Sin mirar una tabla de valores, ¿existe una manera eficiente de saber qué tamaños de montones en el juego de Grundy tienen una estrategia ganadora para que el siguiente jugador se mueva?" entonces la respuesta es básicamente "no sabemos", pero se ha calculado una tabla hasta

2^{35}

$2^{35}$ .

CS1

@Marcas. Creo que me respondió (es por eso que pregunto aquí en los comentarios). ¿Me puede dar un ejemplo para un tamaño de pila más grande que

0

$0$ que no hay una estrategia ganadora para ello? ¡Gracias!

Marcas.

@CS1 En Nim, no existe. En el juego de Grundy, "no tienes una estrategia ganadora cuando la suma mínima es igual a 0", por lo que según la tabla de la publicación de Matthew Daly, 1, 2, 4, 7, 10 y 20 son todos ejemplos. .

¿Cómo puedo saber si una pila en "Grundy's game" tiene una estrategia ganadora?

CS1

Respuestas (1)

usuario694818

CS1

usuario694818

CS1

usuario694818

CS1

Marcas.

CS1

Marcas.

CS1

Marcas.

Encuentra el número de Grundy de la posición inicial y haz el primer movimiento en una estrategia ganadora para el siguiente juego

¿Cómo jugar un movimiento ganador en este tablero de Nim?

Probabilidad de que dos elementos particulares se agrupen en una partición aleatoria con tamaños fijos

Un gráfico máximo conectado GGG sin ciclos de longitud de al menos k+1k+1k+1 tiene |V(G)|≤k|V(G)|≤k|V(G)| \leq k o tiene un vértice cortado cuando k≥2k≥2k \geq 2

Determinar si la relación dada es una relación de equivalencia

Para la relación R=∅R=∅R = \emptyset en {1,2,3}{1,2,3}\{1, 2, 3\}, ¿es reflexiva, simétrica, transitiva?

Prueba del teorema de Caratheodory (para conjuntos convexos) usando el lema de Radon

¿Trayectorias de coeficientes binomiales?

Una pregunta sobre un caso especial del principio de inclusión-exclusión

Parejas sentadas alrededor de 2 mesas