Sam y Hugo juegan con $n$ monedas, todas con $A$ en una cara y $S$ en la otra. Las monedas están puestas en fila sobre la mesa. Sam y Hugo se turnan. En su turno, Sam puede voltear una o más monedas, siempre que no voltee dos adyacentes; mientras Hugo elige exactamente dos monedas adyacentes y las voltea. Al comenzar el juego, todas las monedas muestran $A$. Sam juega primero y gana si todas las monedas muestran $S$ simultáneamente en cualquier momento. Halla todos los $n\geq 1$ con los que Hugo puede evitar que Sam gane.
Solución
Solución:
El caso $n=1,2$ es trivial que Sam gana. Si $n=3$, Sam voltea las monedas de los extremos y sin importar la pareja que Hugo elija, quedan dos monedas con $S$ y una con $A$, por lo que sam voltea esa moneda y gana. Si $n=4$, Sam voltea los extremos otra vez y Hugo puede o autoperder o voltear las adyacentes extremas, por lo que cuando Hugo juege van a quedar las monedas intercaladas ($SASA, \ ASAS$), ganando así Sam.
Vamos a demostrar que para $n \geq 5$, Hugo necesita tener 3 monedas adyacentes de la forma $AAA$ y que ninguna de las 3 monedas sean monedas del extremo de la fila para evitar que Sam gane. Si tiene esta configuración:
Si es turno de Sam, sam puede mover o la moneda central (y otras monedas no adyacentes) o las dos monedas de los extremos (y otras monedas no adyacentes).
Si Sam mueve la moneda central, Hugo va a mover esa moneda y una del extremo. Entonces Sam puede mover o la otra moneda del extremo o la moneda central otra vez. Si mueve la central, se regresa a la configuración. Si mueve la del extremo, Hugo va a mover una moneda del extremo y la adyacente a esta que no sea la central y tiene o la misma configuración o la configuración invertida.
Si Sam mueve las monedas del extremo, entonces Hugo hace el mismo paso de arriba y se regresa a la configuración.
Si Sam mueve únicamente una moneda del extremo, entonces Hugo la voltea con la moneda adyacente que no pertenezca a la configuración.
En caso de que sea Turno de Hugo, simplemente no va a querer tocar esa configuración de monedas. Para el caso $n=5$ donde puede existir la configuración $SAAAS$ y entonces va a tener que tocar a esas monedas, entonces Hugo mueve las 2 monedas extremas de su preferencia (siempre que la moneda del extremo tenga una $S$) y se regresa a la configuración.
Es así como para $n\geq 5$, Sam nunca puede ganar.
