Encuentra una estrategia ganadora en un juego de piedras.

Alice y Bob juegan el siguiente juego: Hay montones de piedras y en cada turno el jugador puede hacer una de las siguientes cosas: Quitar una piedra de un montón, o tomar dos montones con X y y piedras en ellos y reemplazarlos con 1 pila de X y piedras El jugador que no tiene movimiento pierde. ¿Quién tiene la estrategia ganadora?

La respuesta puede depender de la cantidad de pilas y la cantidad de piedras en cada pila. Creo que obtuve una solución inductiva extremadamente fea. Lo que obtuve es que el primer jugador gana si y solo si hay un número impar de piedras, o si hay un número par de piedras y una cantidad par positiva de montones con una cantidad par de piedras en ellos. Aunque podría estar equivocado en alguna parte. ¿Alguien tiene algo elegante?

quisiste decir X + y ?
@Aqua No. Quise decir X y
@ BrianM.Scott Tienes razón, edité mi publicación, el criterio era incorrecto.
Si hay uno o cero montones de piedras con más de una piedra, el primer jugador gana si el número total de piedras es impar y el segundo jugador gana si hay un número par de piedras.
@ quantus14 Sí, escribí el resultado que obtuve en la publicación. Lo que escribiste es un caso especial.
@Omer Es por eso que es un comentario, no una respuesta. No veo nada de malo en publicar información relevante sobre el problema como un comentario.

Respuestas (1)

Una situación consiste en mi de tamaño uniforme y o montones no vacíos de tamaño impar. Afirmo que ganar o perder depende sólo de ( mi , o ) . Dejar W Sea el conjunto de posiciones ( mi , o ) que están ganando y L el conjunto de ( mi , o ) que están perdiendo posiciones.

Afirmar. Tenemos

W = { ( mi , o ) ∣ o  extraño ∨ ( mi  incluso ∧ mi ≠ 0 ) }
y
L = { ( mi , o ) ∣ o  incluso ∧ ( mi  extraño ∨ mi = 0 ) } .

Prueba. Dado que el juego debe terminar después de un número finito de movimientos, basta con mostrar que cada movimiento válido de una situación ∈ L conduce a una situación ∈ W , y en para cada situación ∈ W , existe un movimiento válido a una situación ∈ L .

Comencemos con ( mi , o ) ∈ L :

Primer caso: o es par y mi = 0 . Quitar una piedra de cualquier montón (necesariamente impar) disminuye o a un número impar, por lo tanto nos lleva a W . La combinación de dos montones (necesariamente impares) también disminuye o por uno, por lo tanto nos lleva a W . Concluimos que ( o , 0 ) ∈ L por impar o .

Segundo caso: o es par y mi extraño. Quitar una piedra de un montón impar o combinar dos montones impares o combinar un montón impar y uno par, disminuye o a impar, por lo tanto nos lleva a W Quitar una piedra de un montón uniforme aumenta o a impar, por lo tanto nos lleva a W . Finalmente, combinar dos montones pares (que solo es posible si mi ≥ 3 ) nos lleva a ( mi ′ , o ′ ) = ( mi − 1 , o ′ ) con mi ′ parejo y positivo, así que de nuevo a W .

Entonces, de hecho, cada movimiento válido de una situación ∈ L nos lleva a una situación ∈ W .

A continuación considere ( mi , o ) ∈ W :

Primer caso: mi es uniforme y positivo. Si o es par, podemos combinar dos montones pares para llegar a ( mi ′ , o ′ ) = ( mi − 1 , o ) ∈ L . Si o es impar, podemos sacar una piedra de uno de los montones pares y llegar a ( mi ′ , o ′ ) = ( mi − 1 , o + 1 ) ∈ L .

Segundo caso: o es raro y mi = 0 . Al quitar una piedra de un montón extraño, llegamos a ( mi ′ , o ′ ) = ( 1 , o − 1 ) ∈ L o (si vaciamos un montón) ( mi ′ , o ′ ) = ( 0 , o − 1 ) ∈ L .

Tercer caso: o es raro y mi es impar. Combina un montón par e impar para llegar a ( mi ′ , o ′ ) = ( mi , o − 1 ) ∈ L .

Estos casos lógicamente abarcan todos W . De hecho, de cada situación en W , existe un movimiento válido para L . ◻

¡Muy buena solución! ¡Gracias!
Encuentra una estrategia ganadora en un juego de piedras.
RespuestasAquíPolítica de privacidad1y, 1v