Juegos de piedra otra vez

Question

Dos jugadores están jugando una piedra de selección de juego.

Hay algunos montones de piedras. El número de piedras en cada pila es dado.

Cada jugador toma de acción en las vueltas siguientes reglas:

• El uno en su turno, elige una pila de piedras. Vamos a denotar el número de A.
• A continuación, el mismo jugador elige un número B con 0<2*B<=A.
• 2B piedras se mueven desde la pila original,
• y una pila nueva con-B las piedras se agrega.

A continuación, uno que no puede tomar una acción como por encima de las reglas de describir perderá el juego.

Supongamos que cada uno es lo suficientemente inteligente. Determinar si el primero o el segundo va a ganar.

Este problema es muy común en la piedra de juego. La solución más común es calcular las ratas Sprague-Grundy valor de la función como de la definición y, a continuación, encontrará algunas reglas. Después de esta prueba para probar las reglas que tiene para todas las situaciones.

Mi problema es que la SG de los valores de la función en los casos pequeños parecen muy irregular. Alguien me puede ayudar? O si hay otra solución?

sg[0] = 0, sg[1] = 0, sg[2] = 1, sg[3] = 0

sg[4] = 0, sg[5] = 1, sg[6] = 2, sg[7] = 2

sg[8] = 1, sg[9] = 0, sg[10] = 0, sg[11] = 1

sg[12] = 0, sg[13] = 0, sg[14] = 1, sg[15] = 2

sg[16] = 2, sg[17] = 1, sg[18] = 4, sg[19] = 4

sg[20] = 1, sg[21] = 4, sg[22] = 4, sg[23] = 1

sg[24] = 2, sg[25] = 2, sg[26] = 1, sg[27] = 0

sg[28] = 0, sg[29] = 1, sg[30] = 0, sg[31] = 0

sg[32] = 1, sg[33] = 2, sg[34] = 2, sg[35] = 1

sg[36] = 0, sg[37] = 0, sg[38] = 1, sg[39] = 0

sg[40] = 0, sg[41] = 1, sg[42] = 2, sg[43] = 2

sg[44] = 1, sg[45] = 4, sg[46] = 4, sg[47] = 1

sg[48] = 4, sg[49] = 4, sg[50] = 1, sg[51] = 2

sg[52] = 2, sg[53] = 1, sg[54] = 7, sg[55] = 7

sg[56] = 1, sg[57] = 7, sg[58] = 7, sg[59] = 1

sg[60] = 2, sg[61] = 2, sg[62] = 1, sg[63] = 7

sg[64] = 7, sg[65] = 1, sg[66] = 7, sg[67] = 7

sg[68] = 1, sg[69] = 2, sg[70] = 2, sg[71] = 1

sg[72] = 4, sg[73] = 4, sg[74] = 1, sg[75] = 4

sg[76] = 4, sg[77] = 1, sg[78] = 2, sg[79] = 2

sg[80] = 1, sg[81] = 0, sg[82] = 0, sg[83] = 1

sg[84] = 0, sg[85] = 0, sg[86] = 1, sg[87] = 2

sg[88] = 2, sg[89] = 1, sg[90] = 0, sg[91] = 0

sg[92] = 1, sg[93] = 0, sg[94] = 0, sg[95] = 1

sg[96] = 2, sg[97] = 2, sg[98] = 1, sg[99] = 4

Answer 1

El SG-función está definida por $SG(n) := mex\{SG(n-2m) \stackrel{*}{+} SG(n-m) : 0 < 2m \leq n\}$. El siguiente patrón emerge cuando usted mira a $SG(n)$ $n$ mod $9$ fijo:

0 0 1 0 0 1 2 2 1
0 0 1 0 0 1 2 2 1
4 4 1 4 4 1 2 2 1
0 0 1 0 0 1 2 2 1
0 0 1 0 0 1 2 2 1
4 4 1 4 4 1 2 2 1
7 7 1 7 7 1 2 2 1
7 7 1 7 7 1 2 2 1
4 4 1 4 4 1 2 2 1
0 0 1 0 0 1 2 2 1
0 0 1 0 0 1 2 2 1
4 4 1 4 4 1 2 2 1
0 0 1 0 0 1 2 2 1
0 0 1 0 0 1 2 2 1
4 4 1 4 4 1 2 2 1
7 7 1 7 7 1 2 2 1
7 7 1 7 7 1 2 2 1
4 4 1 4 4 1 2 2 1
8 8 1 8 8 1 2 2 1
8 8 1 8 8 1 2 2 1
4 4 1 4 4 1 2 2 1
8 8 1 8 8 1 2 2 1
8 8 1 8 8 1 2 2 1
4 4 1 4 4 1 2 2 1
7 7 1 7 7 1 2 2 1
7 7 1 7 7 1 2 2 1
4 4 1 4 4 1 2 2 1
0 0 1 0 0 1 2 2 1
0 0 1 0 0 1 2 2 1
4 4 1 4 4 1 2 2 1
0 0 1 0 0 1 2 2 1
0 0 1 0 0 1 2 2 1
4 4 1 4 4 1 2 2 1
7 7 1 7 7 1 2 2 1
7 7 1 7 7 1 2 2 1
4 4 1 4 4 1 2 2 1
0 0 1 0 0 1 2 2 1
0 0 1 0 0 1 2 2 1
4 4 1 4 4 1 2 2 1
0 0 1 0 0 1 2 2 1
0 0 1 0 0 1 2 2 1
4 4 1 4 4 1 2 2 1
7 7 1 7 7 1 2 2 1
7 7 1 7 7 1 2 2 1
4 4 1 4 4 1 2 2 1
8 8 1 8 8 1 2 2 1
8 8 1 8 8 1 2 2 1
4 4 1 4 4 1 2 2 1
8 8 1 8 8 1 2 2 1
8 8 1 8 8 1 2 2 1
4 4 1 4 4 1 2 2 1
7 7 1 7 7 1 2 2 1
7 7 1 7 7 1 2 2 1
4 4 1 4 4 1 2 2 1

Estos son los primeros a $486$ valores. El siguiente número es, por desgracia, $11$. De todos modos, podemos observar el siguiente patrón:

• Cada fila parece tener la forma $x x 1 x x 1 2 2 1$.
• Cada $3k$th ha $x=4$.
• Las otras filas adyacentes coinciden.

Si esto es cierto, toda la función está determinada por los valores de $a(k) := SG(9(3k+1)+1)$, lo que también siguen un patrón agradable cuando nos fix $k$ mod $3$:

0  0  7
0  0  7
8  8  7
0  0  7
0  0  7
8  8  7
11 11 7
11 11 7
8  8  7
0  0  7
0  0  7
8  8  7
0  0  7
0  0  7
8  8  7
11 11 7
11 11 7
8  8  7
13 13 7
13 13 7
8  8  7
13 13 7
13 13 7
8  8  7
11 11 7
11 11 7
8  8  7
0  0  7
0  0  7
8  8  7
0  0  7
0  0  7
8  8  7
11 11 7
11 11 7
8  8  7
0  0  7
0  0  7
8  8  7
0  0  7
0  0  7
8  8  7
11 11 7
11 11 7
8  8  7
13 13 7
13 13 7
8  8  7
13 13 7
13 13 7
8  8  7
11 11 7
11 11 7
8  8  7
14 14 7
14 14 7
8  8  7
14 14 7
14 14 7
8  8  7
11 11 7

El patrón es similar a la de arriba: Cada fila tiene la forma $x x 7$, donde cada tercer $x$$8$, y el otro adyacentes que coinciden. Ahora bien, si esto es cierto, también, $a$ sólo depende de los valores de $a(3(3j+1)+1)$, que a su vez satisfacer un patrón similar (las filas tienen ahora la forma $x x 11$, y uno de cada tres $x$$13$). No sé si este tipo de análisis va a resolver el juego, pero que ya muestra que el SG-función contiene una gran cantidad de "anidada" periodicidad. Y tal vez esto ya es suficiente para determinar al $SG(n)=0$, es decir, cuando el segundo jugador tiene una estrategia ganadora.