OMEO 2020 NA P3

Problemas que aparecen en el Archivo de Enunciados.
Avatar de Usuario
Tomás Morcos Porras

COFFEE - Mención-COFFEE Matías Saucedo OFO - Mención-OFO 2020
Mensajes: 81
Registrado: Dom 13 Oct, 2019 5:04 pm
Medallas: 2
Nivel: 2
Ubicación: Córdoba, Córdoba

OMEO 2020 NA P3

Mensaje sin leer por Tomás Morcos Porras » Vie 07 Feb, 2020 12:35 pm

Mauri y Luigi juegan al siguiente juego. Inicialmente hay una pila con $n$ piedras. Comenzando por Mauri, en cada turno un jugador puede retirar $1$, $3$ o $4$ piedras (siempre que haya al menos esa cantidad de piedras en la pila). Si algún jugador no puede realizar una jugada pierde. Decidir cuál de ellos tiene una estrategia para ganar, independientemente de cómo juegue el otro, si:

(a) $n=15$
(b) $n=2020$
1  
¡Feliz cumpleaños a todos los que cumplen hoy y feliz no cumpleaños a todos los que no cumplen hoy!

Avatar de Usuario
Tomás Morcos Porras

COFFEE - Mención-COFFEE Matías Saucedo OFO - Mención-OFO 2020
Mensajes: 81
Registrado: Dom 13 Oct, 2019 5:04 pm
Medallas: 2
Nivel: 2
Ubicación: Córdoba, Córdoba

Re: OMEO 2020 NA P3

Mensaje sin leer por Tomás Morcos Porras » Vie 07 Feb, 2020 2:29 pm

Lo más largo que escribí en el foro xd
Spoiler: mostrar
Llamemos $p_k$ a la piedra en la posición $k$, siendo $p_1$ la piedra de más abajo y $p_n$ la de más arriba. Llamemos ganadora a una posición siempre que tenga una manera de dejar al rival en una posición perdedora, y perdedora a la que solo puede dejar al rival en posiciones ganadoras.
Veamos primero que, con $n=7$:
Spoiler: mostrar
Spoiler: mostrar
$p_0$ sería la primera posición perdedora, porque el jugador que empiece su turno en esta pierde automáticamente.
$p_1$ es ganadora, porque el jugador que empiece acá puede ganar sacando una piedra y dejando al rival en $p_0$.
El jugador que empiece en $p_2$ tiene una sola jugada habilitada: sacar una piedra de la pila y dejar al rival en $p_1$, por lo que $p_2$ es perdedora.
Desde $p_3$ y $p_4$, se puede llegar a $p_0$ en un movimiento, por lo que son ganadoras.
Desde $p_5$ y $p_6$, se puede llegar a $p_2$ en un movimiento (sacando $3$ y $4$ piedras respectivamente), por lo que son ganadoras
$p_7$ es perdedora, porque las jugadas posibles dejan al otro jugador en $p_6$, $p_4$ o $p_3$
Quedan ordenadas:
$p_7$
$p_6$
$p_5$
$p_4$
$p_3$

$p_2$
$p_1$
$p_0$
Sea ahora $p_x$ perdedora. Se ve que:
Spoiler: mostrar
Hay solo dos casos, que $p_{x+2}$ sea perdedora o que $p_{x-2}$ lo sea.
Para $p_{x+2}$,
Spoiler: mostrar
De $p_x$ hasta $p_{x+7}$, se justifican igual que de $p_0$ a $p_7$.
$p_{x-1}$, $p_{x-3}$ y $p_{x-4}$ son ganadoras, porque si no, de $p_x$ se podría llegar a una perdedora, y sería ganadora.
$p_{x-2}$ es ganadora porque se puede llegar de $p_{x+2}$.
$p_{x-1}$ gana, pero $p_{x-2}$ y $p_{x-4}$ también, y, como tiene que poder llegar a una que pierda, $p_{x-5}$ es perdedora.
De $p_{x-5}$ se puede llegar a $p_{x-6}$, por lo que esta es ganadora
Desde $p_{x-3}$, se llega a $p_{x-4}$ y $p_{x-6}$, por lo que $p_{x-7}$ es perdedora
$p_{x+7}$
$p_{x+6}$
$p_{x+5}$
$p_{x+4}$
$p_{x+3}$

$p_{x+2}$
$p_{x+1}$
$p_x$
$p_{x-1}$
$p_{x-2}$
$p_{x-3}$
$p_{x-4}$

$p_{x-5}$
$p_{x-6}$
$p_{x-7}$

Para el caso contrario, por la misma lógica, sale que

$p_{x+7}$
$p_{x+6}$
$p_{x+5}$
$p_{x+4}$
$p_{x+3}$
$p_{x+2}$
$p_{x+1}$

$p_x$
$p_{x-1}$
$p_{x-2}$
$p_{x-3}$
$p_{x-4}$
$p_{x-5}$
$p_{x-6}$

$p_{x-7}$
Desde donde sale que $p_{x-7}$ y $p_{x+7}$ son ambas perdedoras también. Por esto, como $p_0$ y $p_2$ son perdedoras, sabemos que todas las piedras en posiciones $p_{7\times a}$ y $p_{7\times a+2}$ (con $a$ entero) son todas las perdedoras y todas las otras son ganadoras.
Finalmente, $15=7\times 2+1$ y $2020=7\times 288+4$, por lo que ambas son ganadoras y en ambos casos gana Mauri.
¡Feliz cumpleaños a todos los que cumplen hoy y feliz no cumpleaños a todos los que no cumplen hoy!

Responder