Cono Sur 2006 P2

Matías

OFO - Medalla de Bronce FOFO Pascua 2017 - Medalla OFO - Medalla de Plata
Mensajes: 140
Registrado: Mar 06 Oct, 2015 7:59 pm
Medallas: 4
Nivel: 2

Cono Sur 2006 P2

Mensaje sin leer por Matías » Mié 25 Jul, 2018 6:33 pm

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
Mensajes: 14
Registrado: Mar 26 Jun, 2018 1:59 am
Nivel: Exolímpico

Re: Cono Sur 2006 P2

Mensaje sin leer por juandodyk » Vie 27 Jul, 2018 7:36 pm

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
Mensajes: 685
Registrado: Vie 16 Sep, 2016 6:58 pm
Medallas: 1
Nivel: Exolímpico
Ubicación: Rosario
Contactar:

Re: Cono Sur 2006 P2

Mensaje sin leer por Gianni De Rico » Vie 27 Jul, 2018 7:38 pm

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.
[math]

Responder