Problema 3 Cono Sur 2016

Problemas que aparecen en el Archivo de Enunciados.
Avatar de Usuario
Nacho

Colaborador-Varias OFO - Jurado-OFO 2015 OFO - Jurado-OFO 2016
Mensajes: 563
Registrado: Dom 17 Oct, 2010 10:28 pm
Medallas: 3
Nivel: Exolímpico

Problema 3 Cono Sur 2016

Mensaje sin leer por Nacho »

Alrededor de una circunferencia hay marcadas [math] posiciones, con una ficha en una de ellas. Una movida legítima es mover la ficha o bien a 1 posición o bien a 4 posiciones desde su ubicación, en el sentido de las agujas del reloj. La restricción es que la ficha no puede ocupar la misma posición más de una vez. Los jugadores [math] y [math] se turnan en hacer movidas. [math] es el que mueve primero. El jugador que no puede hacer su movida pierde. Determinar cuál de los dos jugadores tiene estrategia ganadora.
"Though my eyes could see I still was a blind man"
Avatar de Usuario
Emerson Soriano

OFO - Mención-OFO 2015 OFO - Medalla de Oro-OFO 2016 OFO - Medalla de Plata-OFO 2017 OFO - Medalla de Bronce-OFO 2018 OFO - Mención-OFO 2020
OFO - Medalla de Plata-OFO 2022
Mensajes: 826
Registrado: Mié 23 Jul, 2014 10:39 am
Medallas: 6

Re: Problema 3 Cono Sur 2016

Mensaje sin leer por Emerson Soriano »

Spoiler: mostrar
Supongamos sin pérdida de generalidad que la ficha está inicialmente en la posición [math]. Cuando un jugador avanza [math] posición, diremos que hizo una movida del tipo [math], de lo contrario hará una movida del tipo [math]. Diremos que la posición [math] está gastada, si la ficha estuvo en la posición [math] (en algún momento).

Gana [math]. En efecto, [math] empieza haciendo una movida del tipo [math], es decir, pone la ficha en la posición [math]. Luego, a partir de ese momento, sin importar como juegue [math], la estrategia del jugador [math] es hacer lo contrario de [math], es decir, el jugador [math] moverá la ficha [math] posiciones, con respecto a su jugada anterior. De ese modo se garantiza que [math] pone la ficha en la posición [math] (su última jugada de la primera ronda, es decir, su última jugada antes que la ficha de una vuelta). Luego, continuando con la estrategia, en la segunda ronda [math] juega por primera vez colocando la ficha en la posición [math]:
[math]
y esto garantiza que en su última jugada de la segunda ronda, [math] pone su ficha en la posición [math]. Luego, [math] por primera vez, en la tercera ronda, pone la ficha en la posición [math]. Así, se garantiza que [math], juega por última vez en la tercera ronda colocando su ficha en la posición [math]. Todo esto está ocurriendo suponiendo que [math] juega correctamente, es decir, que [math] no haya perdido antes. Ahora, [math] no puede realizar una movida del tipo [math], pues [math] es una posición gastada, pero tampoco puede realizar una movida del tipo [math], pues [math] también es una posición gastada.

Por lo tanto, [math] pierde y [math] tiene la estrategia ganadora.
usuario250

OFO - Jurado-OFO 2015
Mensajes: 236
Registrado: Vie 30 Dic, 2011 12:30 pm
Medallas: 1

Re: Problema 3 Cono Sur 2016

Mensaje sin leer por usuario250 »

Hay un pequeño problema
Spoiler: mostrar
Cuando A "coloca" la ficha en la posición 2, la posición 2 puede estar gastada. Esto es, cuando A, previamente, puso la ficha en la posición 3, puede haber pasado que en el movimiento anterior B haya puesto la ficha en la posición 2, por lo que gastó dicha posición.
Emerson Soriano escribió:
Spoiler: mostrar
Supongamos sin pérdida de generalidad que la ficha está inicialmente en la posición [math]. Cuando un jugador avanza [math] posición, diremos que hizo una movida del tipo [math], de lo contrario hará una movida del tipo [math]. Diremos que la posición [math] está gastada, si la ficha estuvo en la posición [math] (en algún momento).

Gana [math]. En efecto, [math] empieza haciendo una movida del tipo [math], es decir, pone la ficha en la posición [math]. Luego, a partir de ese momento, sin importar como juegue [math], la estrategia del jugador [math] es hacer lo contrario de [math], es decir, el jugador [math] moverá la ficha [math] posiciones, con respecto a su jugada anterior. De ese modo se garantiza que [math] pone la ficha en la posición [math] (su última jugada de la primera ronda, es decir, su última jugada antes que la ficha de una vuelta). Luego, continuando con la estrategia, en la segunda ronda [math] juega por primera vez colocando la ficha en la posición [math]:
[math]
y esto garantiza que en su última jugada de la segunda ronda, [math] pone su ficha en la posición [math]. Luego, [math] por primera vez, en la tercera ronda, pone la ficha en la posición [math]. Así, se garantiza que [math], juega por última vez en la tercera ronda colocando su ficha en la posición [math]. Todo esto está ocurriendo suponiendo que [math] juega correctamente, es decir, que [math] no haya perdido antes. Ahora, [math] no puede realizar una movida del tipo [math], pues [math] es una posición gastada, pero tampoco puede realizar una movida del tipo [math], pues [math] también es una posición gastada.

Por lo tanto, [math] pierde y [math] tiene la estrategia ganadora.
Avatar de Usuario
Emerson Soriano

OFO - Mención-OFO 2015 OFO - Medalla de Oro-OFO 2016 OFO - Medalla de Plata-OFO 2017 OFO - Medalla de Bronce-OFO 2018 OFO - Mención-OFO 2020
OFO - Medalla de Plata-OFO 2022
Mensajes: 826
Registrado: Mié 23 Jul, 2014 10:39 am
Medallas: 6

Re: Problema 3 Cono Sur 2016

Mensaje sin leer por Emerson Soriano »

Tienes razón. Cambió la cosa, intentaré de nuevo!
usuario250

OFO - Jurado-OFO 2015
Mensajes: 236
Registrado: Vie 30 Dic, 2011 12:30 pm
Medallas: 1

Re: Problema 3 Cono Sur 2016

Mensaje sin leer por usuario250 »

Tranqui que a mi tampoco me salió todavía.
Parece un problema interesante.
Avatar de Usuario
jhn

OFO - Medalla de Plata-OFO 2018
Mensajes: 520
Registrado: Mié 10 Oct, 2012 3:25 pm
Medallas: 1
Nivel: Otro
Ubicación: Venezuela

Re: Problema 3 Cono Sur 2016

Mensaje sin leer por jhn »

Spoiler: mostrar
[math] tiene una estrategia ganadora. Numeremos las posiciones de 1 a 2016, con la ficha inicialmente en 1. [math] comienza por mover la ficha de 1 a 2. Ahora, mientras [math] avance 4 posiciones, sin llegar a 2016, [math] avanza una. Así se van gastando las posiciones congruentes con 1 ó 2 módulo 5. Supongamos que luego de gastar [math] y [math] (con [math]), [math] decide avanzar sólo una posición a [math]. Entonces [math] mueve a [math], y en lo sucesivo si [math] avanza [math], [math] avanza [math] (llamemos a este procedimiento "alternar"). De este modo [math] llegará a 2014, [math] sólo podrá mover a 2015, [math] mueve a 3, y continúa alternando (lo cual siempre será posible pues moverá a posiciones [math], que están libres) hasta llegar a [math]. Ahora [math] sólo puede mover a [math], [math] mueve a [math] y gana pues las 4 posiciones siguientes están gastadas.
Supongamos en cambio que en la primera vuelta [math] avance siempre de a 4 hasta llegar a 2016. Entonces [math] mueve a la posición 4, y continúa alternando hasta llegar a 2014. Ahora [math] sólo podrá mover a 2015, [math] mueve a 3 y gana, pues tanto la posición 4 como la 7 están gasradas.
Todo problema profana un misterio; a su vez, al problema lo profana su solución.
Responder