Variación de Nim, en la que hay que dividir una pila en cualquier número de montones.

Question

Estoy aprendiendo los fundamentos de la teoría combinatoria de juegos ( juegos imparciales ). Después de aprender sobre la descomposición de un juego en la suma de juegos, me siento cómodo con los juegos que se pueden dividir en la suma de juegos de 1 pila. La situación está más o menos clara para mí: Tengo que encontrar el gráfico del juego, calcular los valores de Sprague-Grundy y utilizarlos para encontrar la solución a un juego.

Pero no sé realmente qué hacer en caso de que no pueda descomponer un juego en partidas de 1 pila. Aquí hay un ejemplo:

Tienes montones de piedras, la gente alterna los turnos, la persona que no puede hacer un movimiento pierde. Durante el movimiento, un jugador puede seleccionar cualquiera de los dividir las piedras que contiene en un número cualquiera de montones desiguales que no haya dos montones nuevos con el mismo número de piedras.

---

Tengo un gran problema al analizar el subjuego de 1 pila (calcular los valores de grundy para la pila de $1, 2, 3, ... n$ piedras en la pila), porque después de cada movimiento 1 pila se divide en más pilas.

¿Cómo debo analizar estos juegos?

Answer 1

No es difícil de usar Jyrki de hacer una tabla de valores de Sprague-Grundy de pequeños montones individuales:

$$\begin{array}{rcc} \textbf{heap size}:&0&1&2&3&4&5&6&7&8&9&10&11&12&13&14&15&16\\ \textbf{S-G value}:&0&0&0&1&0&2&3&4&0&5&6&7&8&9&10&11&12 \end{array}$$

• Para $n=6$ las posibles divisiones son $\langle 5,1\rangle,\langle 4,2\rangle$ y $\langle 3,2,1\rangle$ con valores S-G $2$ , $0$ y $1$ respectivamente, por lo que el valor S-G de $6$ es $3$ .
• Para $n=7$ las posibles divisiones son $\langle 6,1\rangle,\langle 5,2\rangle,\langle 4,3\rangle$ y $\langle 4,2,1\rangle$ con los valores respectivos $3$ , $2$ , $1$ y $0$ por lo que el valor de $7$ es $4$ .
• Para $n=8$ : $\langle 7,1\rangle,\langle 6,2\rangle,\langle 5,3\rangle,\langle 5,2,1\rangle$ y $\langle 4,3,1\rangle$ con los valores respectivos $4$ , $3$ , $2\oplus 1=3$ , $2$ y $1$ por lo que el valor de $8$ es $0$ .
• Para $n=9$ ; $\langle 8,1\rangle,\langle 7,2\rangle,\langle 6,3\rangle,\langle 5,4\rangle,\langle 6,2,1\rangle,\langle 5,3,1\rangle$ y $\langle 4,3,2\rangle$ con valores $0$ , $4$ , $3\oplus1=2$ , $2$ , $3$ , $2\oplus 1=3$ y $1$ por lo que el valor de $9$ es $5$ .
• Para $n=10$ : $\langle 9,1\rangle,\langle 8,2\rangle,\langle 7,3\rangle,\langle 6,4\rangle,\langle 7,2,1\rangle,\langle 6,3,1\rangle,\langle 5,4,1\rangle,\langle 5,3,2\rangle$ y $\langle 4,3,2,1\rangle$ con los valores respectivos $5$ , $0$ , $4\oplus1=5$ , $3$ , $4$ , $3\oplus1=2$ , $2$ , $2\oplus 1=3$ y $1$ por lo que el valor de $10$ es $6$ .
• Para $n=11$ los valores de las posiciones alcanzables son $6,5,1,4,1,0,5,3,2,2,3$ por lo que el valor de $11$ es $7$ .
• Para $n=12$ los valores de las posiciones alcanzables son $7,6,4,0,6,5,1,4,1,5,3,3,2,2$ por lo que el valor de $12$ es $8$ .
• Para $n=13$ los valores de las posiciones alcanzables son $8,7,7,5,2,7,6,4,0,6,1,2,5,3$ por lo que el valor de $13$ es $9$ .
• Para $n=14$ los valores de las posiciones alcanzables son $9,8,6$ , $6,7,3$ , $7,7,5$ , $2,7,4$ , $0,6,5$ , $0,1$ , $4,1,3$ por lo que el valor de $14$ es $10$ .
• Para $n=15$ los valores de las posiciones alcanzables son $10,9,9$ , $7,4,6$ , $4,8,6$ , $6,7,3$ , $7,5,2$ , $7,1,7$ , $1,4,0$ , $6,2,3$ por lo que el valor de $15$ es $11$ .
• Para $n=16$ los valores de las posiciones alcanzables son $11,10,8$ , $8,5,5$ , $1,9,9$ , $7,4,6$ , $4,6,6$ , $7,3,4$ , $3,6,6$ , $7,5,2$ , $7,5,0,2$ por lo que el valor de $16$ es $12$ .

Esperaba que el valor S-G de $16$ sería $0$ , lo que sugiere un patrón de valores que aumenta en $1$ pero bajando a $0$ en cada potencia de $2$ . Desde que eso falló, no tengo ninguna conjetura razonable sobre el patrón real.

Probablemente valga la pena investigar la posibilidad de que para $n\ge 9$ el valor S-G de un montón de $n$ es simplemente $n-4$ Pero tengo la intención de reflexionar sobre ello.

Answer 2

Como Jyrki comentó En este juego, los movimientos descomponen los montones en sumas de montones, y la regla xor se sigue aplicando cuando se tiene una suma de más de dos montones.

Con un poco de código de Mathematica, utilizando simplemente las reglas mex y xor para los valores de Sprague-Grundy, encontré que los valores para una sola pila de tamaño $1$ al tamaño $70$ son: $0,0,1,0,2,3,4,0,5,6,7,\ldots,66$ . En particular, el valor para una sola pila de tamaño $n$ (donde $n>9$ ) parece ser $n-4$ . Este tipo de patrón tiene sentido porque a medida que los números crecen, hay tantas formas de dividir la pila que se puede conseguir cada número anterior como el xor de los valores que se pueden alcanzar.

Sin embargo, no he podido ver un patrón obvio en las jugadas ganadoras, así que no estoy seguro de cómo probar que este patrón continúa para siempre.

---

código:

moves[n_] := moves[n] = 
  Map[If[Union[#] == Sort[#] && Length[#] > 1, #, Nothing] &, 
   IntegerPartitions[n]]; 
mex[list_] := mex[list] = 
  Do[If[Not[MemberQ[list, i - 1]], Return[i - 1]], {i,Length[list] + 1}]; 
nimber[n_] := nimber[n] = 
  mex[Map[Apply[BitXor, Map[nimber, #]] &, moves[n]]];

---

Editar:

Usando cgsuite, podemos llegar mucho más lejos. Si restringimos las reglas para decir que se puede descomponer una pila en un máximo de cinco pilas, entonces los valores de Sprague-Grundy pueden ser calculados muy eficientemente por cgsuite código: hr:=game.heap.HeapRules.MakeRules("&60;!."); hr.NimValues(500)

Con esto, vemos que la división en un máximo de cinco montones es suficiente para que el patrón mencionado anteriormente persista hasta el tamaño $499$ con valor $495$ . La restricción a un máximo de cuatro pilas pone un 0 entre el 12 y el 13, pero continúa un $n-5$ hasta llegar a un tamaño de pila inicial de $499$ también. (Un máximo de tres pilas da muy pocas opciones para un patrón simple).