División de pilas de Nim

Question

Un juego es jugado por dos jugadores y una pila inicial de $n$ centavos ($n\geq 3$). Los jugadores toman turnos para escoger a una de las pilas de monedas en la mesa y su división en dos pilas. Cuando un jugador hace un movimiento que hace que todas las pilas a la altura $1$ o $2$ al final de su turno, ese jugador gana. Que a partir de los valores de $n$ son victorias para cada jugador?

Para todos los valores que he probado, si incluso es el primer jugador gana y si es impar el segundo jugador gana. Si es par, entonces los pilotes se deben dividir en dos pares o de dos probabilidades. Si se trata de dos pares, el siguiente jugador gana una de las divisiones de forma recursiva, pero el primer jugador gana el otro (por lo que el primer jugador gana). Si es impar, sucede lo contrario (el segundo jugador de forma recursiva 'pierde' ambas pilas). Si es impar, entonces debe ser dividido en una extraña e incluso uno de la pila, por lo que el segundo jugador puede elegir a perder el extraño pila y así ganar incluso la pila. PERO esto no toma en cuenta el hecho de que cuando usted tiene un montón de $1$s y $2$s", que se considera terminado para un montón de $n$, pero cuando hay más de una pila, entonces usted todavía puede dividir el $2$s en $1$s y retrasar su vuelta.

Entonces, ¿qué estrategia funciona para todos los valores que garantiza una victoria para uno de los jugadores?

Answer 1

El primer jugador gana si y sólo si se inicia con $1$, $3$, o un número de monedas de un centavo.

Como muchos nim-variantes, este juego tiene una simple condición de que usted gana, porque siempre se puede garantizar que regresar a la misma en su turno hasta llegar a un "final de juego":

Deje $n$ el número de pilas con un número par de monedas de un centavo. Usted puede ganar si y sólo si $n$ es extraño al principio de tu turno (o si se puede ganar de inmediato en ese turno por romper el último grupo de 3 o 4).

A ver que siempre se puede mantener esta afección, considere cómo se mueve cambio $n$:

-La división de un extraño pila de rendimientos incluso una pila y una extraña pila, el aumento de $n$ por 1.

-La división de una, incluso de la pila en dos pilas aumenta el $n$ por 1.

-La división de una, incluso de la pila en dos impares pilas disminuye el $n$ por 1.

En todos estos casos, la paridad de $n$ cambios. Por lo tanto , la paridad de n cambios en cada turno, y lo que si es impar en el inicio de tu turno va a ser incluso en el turno de tu oponente y extraño en su turno de nuevo, es decir que va a ser extraño al principio de todas las vueltas.

Ahora sólo tenemos que examinar el "fin del juego": Cómo evitar darle a su oponente en una posición en la que puede ganar. Si se les podría dar una posición tal, que significa que usted podría darles una posición con sólo una pila de más de 2 centavos: una pila de 3 o 4. Suponiendo que usted no puede adjudicarse la victoria en su turno, esto significa el comienzo de tu turno es uno de los pocos casos. Sólo tenemos que enumerar y mostrar siempre se puede ganar, asumiendo $n$ es impar:

Caso 1 - Hay $2$ pilas de $3$ (por lo tanto un número impar de pilas de $2$): Obviamente, quien divide la primera pila de $3$ pierde, por lo que se turnan para la división de las pilas de $2$. Puesto que hay un número par de ellos al final de cada uno de tus turnos, que finalmente va a tener cero al final de tu turno, obligando a su rival a dividir a una de las pilas de $3$. Usted gana por la separación de los otros.

Caso 2 - No $1$ pila de $3$ $1$ pila de $4$ (por lo tanto un número par de pilas de 2): Retire $1$ centavo de la pila de $4$, obligando a su rival a dividir una pila de $2$ o deje de ganar, la reducción de esta a la del caso 1.

Caso 3 - Hay dos pilas de $4$ (por lo tanto un número impar de pilas de $2$): Quitar ni un céntimo de uno de los montones de $4$. Su rival será obligado a quitar ni un céntimo de la otra pila de $4$, reduciendo a la del caso 1, o dividir una pila de tamaño $2$, la reducción para el caso de $2$.

Caso 4 - Hay una sola pila de $5$ (por lo tanto un número impar de pilas de $2$): aquel que se divide la pila de $5$ va a perder, así que los dos van a ser la división de las pilas de $2$. Pero como siempre hay un número par al final de tu turno, tendrás que dividir la última y ganar.

Caso 5 - Hay una sola pila de $6$, (por lo tanto un número par de pilas de $2$): Dividir la pila de $6$ en dos pilas de $3$. Tu oponente debe dividir una pila de tamaño $2$ o deje de ganar, la reducción a la del caso 1.

Esto muestra que si $n$ es extraño al principio de su turno, usted siempre tiene un movimiento que no deja que su rival para ganar, por lo que finalmente se va a ganar.

Curiosamente, esto significa que cualquier no-estúpido estrategia es óptima , siempre y cuando no dejes que tu rival para ganar en el turno siguiente (y usted gana en su turno si puede), que va a terminar ganando el juego. Así que realmente no se puede "ensuciar" este juego en una manera no evidente, a diferencia de los tradicionales nim.

Answer 2

Como usted dice, una pila es un primer triunfo de jugador, ya que el jugador puede dividir en la coincidencia de los pilotes y el espejo, el otro jugador. El elemento sobre pilotes de 2 no importa, como no va a ser duplicados. Como el primer jugador en esta estrategia, si mi oponente se puede dividir un 2, siempre hay uno para mí split.

Un 3 de pila es también un primer jugador en ganar, como puede dividir 2+1. 5 es el segundo jugador, ya que tienes que ir a 3+2 o 4+1. 7 es el segundo de 3+4 o 6+1 va a 3+3+1 y 5+2 va a 5+1+1.

Answer 3

Aquí para referencia es una tabla de valores de nim por cada posición no trivial con menos de 12 centavos. Se han omitido los montones del tamaño 1. Nim-el valor de 0 indica una posición que es una victoria para el jugador que se mueve cualquier otro valor indica una posición que es una victoria para el siguiente jugador a moverse.

$$\begin{array}{lr} 3 & 1 \\ \hline\\ 4 & 2 \\ \hline\\ 3,2 & 2 \\ 5 & 0 \\ \hline\\ 4,2 & 1 \\ 3,3 & 0 \\ 6 & 2 \\ \hline\\ 3,2,2 & 1 \\ 5,2 & 2 \\ 4,3 & 2 \\ 7 & 0 \\ \hline\\ 4,2,2 & 2 \\ 3,3,2 & 2 \\ 6,2 & 0 \\ 5,3 & 0 \\ 4,4 & 0 \\ 8 & 1 \\ \hline\\ 3,2,2,2 & 2 \\ 5,2,2 & 0 \\ 4,3,2 & 0 \\ 7,2 & 1 \\ 3,3,3 & 0 \\ 6,3 & 1 \\ 5,4 & 1 \\ 9 & 0 \\ \hline\\ 4,2,2,2 & 1 \\ 3,3,2,2 & 0 \\ 6,2,2 & 2 \\ 5,3,2 & 1 \\ 4,4,2 & 2 \\ 8,2 & 0 \\ 4,3,3 & 1 \\ 7,3 & 0 \\ 6,4 & 0 \\ 5,5 & 0 \\ 10 & 1 \\ \hline\\ 3,2,2,2,2 & 1 \\ 5,2,2,2 & 2 \\ 4,3,2,2 & 2 \\ 7,2,2 & 0 \\ 3,3,3,2 & 1 \\ 6,3,2 & 0 \\ 5,4,2 & 0 \\ 9,2 & 1 \\ 5,3,3 & 0 \\ 4,4,3 & 0 \\ 8,3 & 1 \\ 7,4 & 1 \\ 6,5 & 1 \\ 11 & 0 \\ \end{matriz} $$