Selectivo IMO 2019 - Problema 1

jujumas

OFO - Mención OFO - Medalla de Plata FOFO 7 años - Medalla Especial OFO - Oro perfecto FOFO Pascua 2017 - Medalla
OFO - Medalla de Oro FOFO 8 años - Jurado OFO - Jurado
Mensajes: 367
Registrado: Dom 26 Oct, 2014 8:30 pm
Medallas: 9
Nivel: 2

Selectivo IMO 2019 - Problema 1

Mensaje sin leer por jujumas » Jue 11 Abr, 2019 8:16 pm

Sea $n\geq 3$ un entero. En una hoja de papel se marcan el centro y los $n$ vértices de un polígono de $n$ lados. Ana y Beto juegan del siguiente modo: cada uno en su turno elige un vértice y traza el segmento que lo une con uno de sus vértices vecinos o con el centro del polígono, con la condición que ese segmento no se haya trazado en jugadas anteriores. Gana el que logra que luego de su jugada sea posible viajar de cualquier punto marcado a cualquier otro punto marcado recorriendo exclusivamente segmentos trazados a lo largo del juego. Ana juega en primer lugar.
Para cada entero $n\geq 3$, determinar cuál de los dos jugadores tiene estrategia ganadora y dar dicha estrategia.
Nota. Dos vértices son vecinos si el segmento que los une es un lado del polígono.

BrunZo

OFO - Medalla de Bronce FOFO 8 años - Mención Especial OFO - Medalla de Plata
Mensajes: 58
Registrado: Mar 21 Nov, 2017 8:12 pm
Medallas: 3
Nivel: 1

Re: Selectivo IMO 2019 - Problema 1

Mensaje sin leer por BrunZo » Jue 11 Abr, 2019 8:35 pm

Solución:
Spoiler: mostrar
Vamos a demostrar que $n$ impar gana Ana e $n$ par gana Beto. Usaremos inducción:
Los casos $n=3$ y $n=4$ funcionan [se deja como ejercicio al lector probarlo].
Ahora, vamos a demostrar que si se cumple para $n$, se cumple para $n+2$. Tomemos tres vertices consecutivos $A_1A_2A_3$ del polígono $A_1A_2A_3\dots A_{n+2}$. Ahora, construimos otro polígono $B_1B_2B_2\cdots B_n$ donde $B_1$ representa el grupo $A_1A_2A_3$ y $B_i$ representa $A_{i+2}$ para $i>1$. Ahora, Ana o Beto van a aplicar la estrategia para el $n$-ágono $B_1B_2B_2\cdots B_n$ en $A_1A_2A_3\dots A_{n+2}$ de la siguiente forma:
  • Conectar $A_{n+2}A_1$ representa $B_nB_1$ y conectar $A_3A_4$ representa conectar $B_1B_2$.
  • Conectar el primer $A_iO$ con $1\leq i\leq 3$ representa conectar $B_1O$
  • Si el jugador que no tiene la estrategia coloca $A_1A_2$ ó $A_2A_3$, el ganador coloca el otro (el jugador que gana no puede colocar el primero de estos segmentos, ya que no pertenecen al polígono $B_1B_2B_2\cdots B_n$ sobre el cual hace la estrategia).
  • Si el jugador perdedor coloca el segundo $A_iO$ con $1\leq i\leq 3$, el ganador coloca el tercero.
Con todo esto, notamos que la propiedad se cumple en $A_1A_2A_3\dots A_{n+2}$ si y sólo si lo hace en $B_1B_2B_2\cdots B_n$. Entonces, el que tenía estrategia ganadora en $n$, la tiene en $n+2$, y estamos.

Avatar de Usuario
Prillo

Colaborador OFO - Jurado
Mensajes: 398
Registrado: Sab 18 Dic, 2010 8:52 pm
Medallas: 2

Re: Selectivo IMO 2019 - Problema 1

Mensaje sin leer por Prillo » Dom 14 Abr, 2019 9:13 am

@BrunZo me parece que tu idea no funciona:
Spoiler: mostrar
Que pasa si Ana aplica su estrategia de $n=3$ para $n=5$ y se juega asi:
- Ana = $(A_4, A_5) = (B_2, B_3)$
- Beto = $(A_2, O) = (B_1, O)$
- Ana = $(A_4, O) = (B_2, O)$ [Aca ya gana Ana para $n = 3$, pero el juego sigue para $n=5$]
- Beto = $(A_5, O)$.
- No importa que haga Ana gana Beto en la siguiente jugada.

BrunZo

OFO - Medalla de Bronce FOFO 8 años - Mención Especial OFO - Medalla de Plata
Mensajes: 58
Registrado: Mar 21 Nov, 2017 8:12 pm
Medallas: 3
Nivel: 1

Re: Selectivo IMO 2019 - Problema 1

Mensaje sin leer por BrunZo » Dom 14 Abr, 2019 3:01 pm

Prillo escribió:
Dom 14 Abr, 2019 9:13 am
@BrunZo me parece que tu idea no funciona:
Spoiler: mostrar
Que pasa si Ana aplica su estrategia de $n=3$ para $n=5$ y se juega asi:
- Ana = $(A_4, A_5) = (B_2, B_3)$
- Beto = $(A_2, O) = (B_1, O)$
- Ana = $(A_4, O) = (B_2, O)$ [Aca ya gana Ana para $n = 3$, pero el juego sigue para $n=5$]
- Beto = $(A_5, O)$.
- No importa que haga Ana gana Beto en la siguiente jugada.
Spoiler: mostrar
Bueno, tenés razón. Claramente, el error está en
BrunZo escribió:
Jue 11 Abr, 2019 8:35 pm
la propiedad se cumple en $A$ si y sólo si lo hace en $B$.
lo cual es falso. En particular, el problema está en que, al tomar que $B_1=A_1A_2A_3$, se está asumiendo que $A_1A_2A_3$ están conectados.
Igualmente, esto se puede arreglar (creo), haciendo que el ganador conecte $A_1A_2A_3$ verdaderamente.
Explicado así nomás, para el caso par habría que analizar, dependiendo de si Ana usa el centro o no, que pasa al $A_1A_2A_3$ ó $A_1OA_3$ están conectados. Para el caso impar, Ana debería usar sus primeros dos turnos para obtener alguno de los casos de arriba, y se debería reforzar la hipótesis inductiva a "no importa como Ana coloque el primero", para no tener problemas con el primer movimiento de Beto.
Creo que así estaríamos...

Responder