Variación de Nim, donde uno tiene que dividir una pila en cualquier cantidad de pilas.

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

• Para$n=6$las posibles divisiones son$\langle 5,1\rangle,\langle 4,2\rangle$, y$\langle 3,2,1\rangle$, con valores SG$2$,$0$, y$1$, respectivamente, por lo que el valor SG 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 sus respectivos valores$3$,$2$,$1$, y$0$, entonces 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 sus respectivos valores$4$,$3$,$2\oplus 1=3$,$2$, y$1$, entonces 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$, entonces 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 sus respectivos valores$5$,$0$,$4\oplus1=5$,$3$,$4$,$3\oplus1=2$,$2$,$2\oplus 1=3$, y$1$, entonces 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$, entonces 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$, entonces 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$, entonces 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$, entonces 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$, entonces 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$, entonces el valor de$16$es$12$.

Esperaba que el valor SG de$16$sería$0$, lo que sugiere un patrón de valores que aumentan en$1$pero sumergiéndome en$0$en cada potencia de$2$. Dado que eso falló, no tengo una suposición razonable sobre el patrón real.

Probablemente valga la pena investigar la posibilidad de que para$n\ge 9$el valor SG de un montón de$n$es simple$n-4$; Tengo la intención de pensarlo un poco.

Como comentó Jyrki , los movimientos en este juego descomponen montones en sumas de montones, y la regla xor aún se aplica cuando tienes una suma de más de dos montones.

Con un poco de código de Mathematica usando simplemente las reglas mex y xor para los valores de Sprague-Grundy, descubrí que los valores para una sola pila de tamaño$1$medir$70$son:$0,0,1,0,2,3,4,0,5,6,7,\ldots,66$. En particular, el valor de una sola pila de tamaño$n$(dónde$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 puedes lograr cada número anterior como el xor de los valores que puedes alcanzar.

Sin embargo, no he podido ver un patrón obvio en los movimientos ganadores, 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 puede descomponer una pila en cinco pilas como máximo, entonces los valores de Sprague-Grundy se pueden calcular de manera muy eficiente mediante el código cgsuite :hr:=game.heap.HeapRules.MakeRules("&60;!."); hr.NimValues(500)

Con esto, vemos que dividir en cinco montones como máximo es suficiente para que el patrón mencionado anteriormente persista hasta alcanzar el tamaño.$499$con valor$495$. Restringiendo a un máximo de cuatro montones pone un 0 entre 12 y 13, pero continúa un$n-5$patrón a partir de entonces todo el camino hasta un tamaño de pila inicial de$499$también. (A lo sumo tres pilas dan muy pocas opciones para un patrón simple).