Hay$n$ objetos en la tabla. Dos jugadores se turnan. En un movimiento, el jugador puede tomar$x^2$ ($x$ es cualquier entero, los jugadores pueden cambiarlo) objetos. El jugador que no puede hacer ningún movimiento pierde y el otro gana. ¿Cuántas$n$ hay para que el segundo jugador tenga una estrategia ganadora? Creo que hay infinitos$n$, pero no tengo idea de cómo probarlo.
Respuestas
¿Demasiados anuncios?
Definir la posición de la "$k$ " como un escenario donde hay $k$ objetos sobre la mesa en un turno.
Llame a la posición $k$ ganar si un jugador con esa posición tiene una estrategia ganadora (es decir, una estrategia que puede garantizar una victoria, independientemente de los movimientos elegido por el oponente).
Si la posición no es ganar, llame a perder.
Deje $W$ ser el conjunto de todas las posiciones ganadoras, y deje $L$ ser el conjunto de todas las posiciones perdedoras.
Por ejemplo, $1, 3, 4 \in W$$0, 2, 5 \in L$.
Si el juego comienza en una posición perdedora, entonces el jugador $2$ tiene una estrategia ganadora.
La pregunta es: ¿cuántos elementos hace que el conjunto $L$?
Reclamación $L$ es infinito.
Supongamos lo contrario.
A continuación, $L$ tiene un elemento más grande, $m$, dicen.
Claramente debemos tener $m >2$ (desde $5 \in L$).
Ahora considere la posición $n = m^2-1$.
Desde $n > m$, posición $n$ debe ser ganar.
De ello se desprende que para algún entero positivo $k < m^2$, debemos tener $n - k^2 \in L$.
Pero $n-k^2$ no puede ser en $L$, desde
$$n - k^2 \ge n - (m-1)^2 = (m^2-1)-(m-1)^2 = 2m - 2 > m$$
Por lo tanto, tenemos una contradicción.
Por lo tanto, como se afirma, $L$ debe ser infinito.
lesath82
Puntos
163
El juego puede ser completamente definir de forma recursiva. Inicio en $n=1$, el primer jugador toma el objeto y gana. En $n=2$, el primer jugador tiene sólo un movimiento válido, que se está llevando a $1$ objeto, dejando en el segundo jugador en una situación que ya ha sido demostrado ser un ganador. Así que el primer jugador pierde. En $n=3$ el primer jugador tiene al menos un movimiento (de nuevo, teniendo en $1$ objeto) que envía el segundo jugador en una situación en la que ben ha demostrado una perdedora, por lo que el primer jugador gana. A mayor $n$'s de ir en la comprobación de si el primer jugador tiene al menos un movimiento válido para enviar el segundo jugador en una situación que ya ha sido comprobada de perder. Si él no tiene un movimiento como tal, él es forzado a dejar el segundo jugador en una posición ganadora entonces pierde.
Aquí está el ganador de la tabla de $n$ $100$ (el de más a la derecha el número es una posible jugada ganadora para el primer jugador):
