Cono Sur 2006 P2

Problemas que aparecen en el Archivo de Enunciados.
Matías

OFO - Medalla de Bronce-OFO 2016 OFO - Medalla de Bronce-OFO 2017 FOFO Pascua 2017 - Medalla-FOFO Pascua 2017 OFO - Medalla de Plata-OFO 2018 FOFO 8 años - Medalla Especial-FOFO 8 años
OFO - Medalla de Oro-OFO 2019 FOFO Pascua 2019 - Medalla-FOFO Pascua 2019 COFFEE - Mención-COFFEE Ariel Zylber
Mensajes: 206
Registrado: Mar 06 Oct, 2015 7:59 pm
Medallas: 8
Nivel: 3

Cono Sur 2006 P2

Mensaje sin leer por Matías »

Dos personas, $A$ y $B$, juegan quitando monedas de una pila que contiene inicialmente $2006$ monedas. Los jugadores juegan por turnos quitando en cada turno de $1$ a $7$ monedas; cada jugador conserva consigo las monedas que ha quitado. Si un jugador lo desea, puede pasar (no quitar monedas en su turno) pero para ello debe pagar $7$ monedas de las que retiró de la pila en turnos anteriores. Estas monedas se guardan en una caja aparte y ya no intervienen más en el juego. Gana quien retira la última moneda, y $A$ comienza el juego. Determinar cuál de los dos jugadores puede asegurarse la victoria, no importa cómo juegue el otro. Mostrar una estrategia ganadora y explicar por qué es ganadora.
juandodyk

OFO - Medalla de Oro-OFO 2022 OFO - Medalla de Oro-OFO 2023 OFO - Mención-OFO 2024
Mensajes: 42
Registrado: Mar 26 Jun, 2018 1:59 am
Medallas: 3
Nivel: Exolímpico

Re: Cono Sur 2006 P2

Mensaje sin leer por juandodyk »

Spoiler: mostrar
Notar primero que en algún turno a $A$ le toca jugar y hay entre $1$ y $14$ monedas. En efecto, si no, en el último turno en el que le toca jugar a $A$ hay al menos $15$ monedas, pero tras jugar $A$ y $B$ como mucho hay $14$ monedas menos (cada uno saca como mucho $7$), por lo que queda al menos una moneda, y le toca jugar de nuevo a $A$, absurdo.

Voy a mostrar que $A$ tiene la siguiente estrategia ganadora. Debe siempre quitar $7$ monedas de la pila, hasta que, por primera vez, le toca jugar y hay a lo sumo $14$ monedas en la pila (por el párrafo anterior esto sucede). Sea $x$ la cantidad de monedas que quedan en este turno.

Supongamos que $B$ hizo lo mismo que $A$. Entonces como hay $x$ monedas, $x+14k=2006$, donde $k$ es la cantidad de jugadas que hubo de $A$ y luego de $B$; como $x\leqq 14$, y el resto de $2006$ en la división por $14$ es $4$, debe ser $x=4$ (si $x$ es más chico, es $\leqq 4-14<0$, imposible; si es más grande es $\geqq 4+14>14$, imposible). Entonces $A$ quita $4$ monedas y gana.

Si $B$ no hizo lo mismo que $A$ entonces en algún momento sacó menos de $7$ monedas, por lo que conserva menos monedas que $A$. Si $x\leqq 7$, $A$ saca $x$ monedas y gana. Si $x=8$, $A$ pasa. Si $B$ juega, deja a $A$ en la situación anterior, y gana. Entonces $B$ debe pasar. Pero como $B$ conserva menos monedas que $A$, y $A$ puede usar hasta su última moneda, porque conserva un múltiplo de $7$ monedas, siempre que $B$ pase $A$ va a poder pasar. Entonces en algún momento debe jugar, y $A$ gana en el siguiente turno.

Si $x\in \{9, \ldots, 14\}$, $A$ saca $x-8$ monedas, de manera que en el siguiente turno quedan $8$ monedas. Si $B$ juega, $A$ gana. De nuevo, $A$ puede pasar más veces que $B$, así que en algún momento $B$ juega, y de nuevo $A$ gana.
Avatar de Usuario
Gianni De Rico

FOFO 7 años - Mención Especial-FOFO 7 años OFO - Medalla de Oro-OFO 2019 FOFO 9 años - Jurado-FOFO 9 años COFFEE - Jurado-COFFEE Matías Saucedo OFO - Jurado-OFO 2020
FOFO Pascua 2020 - Jurado-FOFO Pascua 2020 COFFEE - Jurado-COFFEE Carolina González COFFEE - Jurado-COFFEE Ariel Zylber COFFEE - Jurado-COFFEE Iván Sadofschi FOFO 10 años - Jurado-FOFO 10 años
OFO - Jurado-OFO 2021 FOFO 11 años - Jurado-FOFO 11 años OFO - Jurado-OFO 2022 FOFO Pascua 2022 - Jurado-FOFO Pascua 2022 FOFO 12 años - Jurado-FOFO 12 años
OFO - Jurado-OFO 2023 FOFO 13 años - Jurado-FOFO 13 años OFO - Jurado-OFO 2024
Mensajes: 2212
Registrado: Vie 16 Sep, 2016 6:58 pm
Medallas: 18
Nivel: Exolímpico
Ubicación: Rosario
Contactar:

Re: Cono Sur 2006 P2

Mensaje sin leer por Gianni De Rico »

Spoiler: mostrar
La idea es: Si $A$ saca siempre $7$ monedas, entonces va a poder pasar más veces que $B$ cuando sea necesario.

Entonces, $A$ saca siempre $7$ monedas (mientras no deje $7$ o menos y $B$ pueda ganar). Si $B$ saca siempre $7$ monedas, sin pasar, entonces después de $143$ turnos de $A$ y $142$ turnos de $B$, van a quedar $2006-1995=11$ monedas. Si $B$ saca más de $3$ monedas, entonces $A$ saca las restantes y gana, luego, debe sacar como mucho $3$ monedas. Si saca las $3$, ambos deberán pasar para no perder, pero $A$ puede pasar más veces que $B$, por lo que $B$ se verá obligado a sacar monedas, entonces $A$ retira las restantes y gana. Si $B$ saca $b<3$ monedas, entonces $A$ saca $3-b$ monedas, y ambos deben pasar para no perder, pero $A$ puede pasar más veces que $B$ (más aún, $B$ debe ser el que comienza pasando), por lo que $B$ se verá obligado a sacar monedas, entonces $A$ retira las restantes y gana.
Si $B$ pasa o saca menos de $7$ monedas en algún turno, volvemos a llegar a que ambos deben pasar y $A$ puede hacerlo más veces que $B$, por lo que $A$ gana.

Entonces $A$ tiene una estrategia ganadora.
♪♫ do re mi función lineal ♪♫
Responder