Varias pilas de monedas, tomen turnos para la extracción de uno o todos de alguna de las pilas, que obtendrá la última vez, a o B?

Question

esta es una variación de la moneda de la pila de extracción de juego que he visto en varios lugares en línea. En este caso, las propiedades son:

Hay n pilas de monedas de todos los potencialmente diferentes tamaños. Comenzando con el Jugador a, los jugadores a y B se convierte en extraer una o todas las monedas de uno de los montones. La persona que queda sin vuelta posible pierde. ¿Cómo puedo resolver este problema?

Answer 1

Este juego es similar a la de Nim y puede ser resuelto utilizando ratas Sprague-Grundy teorema.

Podemos calcular el Nim-los valores de las pilas en su juego, de ver las opciones disponibles y la búsqueda de los mínimos excluidos elemento, o mex.

Deje $v(n)$ ser el Nim-valor de una pila de tamaño $n$. Entonces:

• Una pila de tamaño $1$ solo puede ser reducido a $0$; $v(1) = mex(\{0\})=*$.
• Una pila de tamaño $2$ puede ser reducido a $0$ o $1$; $v(2) = mex(\{0,v(1)\})=*2$.
• Una pila de tamaño $3$ puede ser reducido a $0$ o $2$; $v(3) = mex(\{0,v(2)\})=*$.
• Una pila de tamaño $4$ puede ser reducido a $0$ o $3$; $v(4) = mex(\{0,v(3)\})=*2$.
• $\ldots$

En resumen, podemos mirar en cada pila como vacío, incluso, o impar.

Answer 2

Le pregunte por Théophile la respuesta, podemos hacer una declaración directa de cómo se juega el juego. Reclamamos el $P$ posiciones, ganado por el jugador anterior, son aquellas que tienen un número par de pilas con un número par de piedras y un número par de pilas que tienen un número impar de piedras, y el $N$ posiciones son el resto. Para probar esto tenemos que mostrar que el terminal de la posición es $P$, que todos los movimientos de $P$ posiciones resultado en $N$ posiciones, y que todos los $N$ posición tiene al menos un mover a un $P$ posición. El terminal de la posición no tiene pilas, por lo que tiene un número par de pilas de cada paridad. De un $P$ posición, cualquier movimiento va a salir un número impar de pilas de la paridad se mudaron. Si las hojas se mueven las piedras en la pila movido en, que también dejará un número impar de los montones de los demás de la paridad, pero no lo necesitamos. Si hay un número impar de montones de uno de paridad y un número par de los otros, tomar un montón entero de la paridad con un número impar de pilas y deje una $P$ posición. Si hay un número impar de pilotes de cada una de paridad, tomar una piedra de una pila con un número par de piedras y esto dejará una $P$ posición. Esto muestra el $N$ $P$ posiciones son, como afirma y da un movimiento específico donde hay un ganador (el $N$ posiciones).