Entrenamiento Cono 2018 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

Entrenamiento Cono 2018 P2

Mensaje sin leer por Matías »

Xavier y Miguel juegan sobre $n$ puntos en una circunferencia donde todos los segmentos entre los puntos son trazados. Xavier empieza y en cada paso los jugadores se alternan coloreando un punto o un segmento en alguno de $n$ colores. Se consideran las siguientes condiciones:
  1. Existen dos puntos con el mismo color.
  2. Existe un segmento que tiene el mismo color que alguno de los puntos que lo definen.
  3. Existen dos segmentos con el mismo color que comparten un punto.
Si alguna de estas condiciones se cumple, entonces gana Miguel. Si ninguna de las condiciones se cumple y todos los puntos y segmentos están coloreados, gana Xavier. ¿Para qué valores de $n$ siempre va a ganar Miguel, sin importar cómo jueguen ambos?
Avatar de Usuario
Kechi

OFO - Medalla de Bronce-OFO 2023 OFO - Medalla de Plata-OFO 2024
Mensajes: 76
Registrado: Mié 21 Sep, 2022 1:41 pm
Medallas: 2
Nivel: 2

Re: Entrenamiento Cono 2018 P2

Mensaje sin leer por Kechi »

Spoiler: mostrar
Para que gane Xavier debe existir alguna coloración de todos los puntos y segmentos tal que ninguna de las tres condiciones se cumplan.

Por la condición i cada punto debe ser de un color distinto. Luego, de cada punto salen $n-1$ segmentos que por las condiciones ii y iii sabemos que son cada uno de cada color posible entre los $n-1$ colores distintos al color con el que se pintó el punto el que salen. Por lo tanto deducimos que dado un color $A$, de cada punto (a excepción del pintado con $A$) sale exactamente un segmento de color $A$. Como cada segmento está determinado por $2$ puntos, la cantidad de puntos totales es el doble de la cantidad de segmentos coloreados de $A$ más $1$, el punto pintado de $A$. Es decir, si gana Xavier entonces $n$ es impar.

Veamos ahora que para cualquier $n$ impar existe una coloración en la que gana Xavier:
Primero deben pintar todos los puntos con los $n$ colores. Luego tomar un color, digamos $A$, y realizar el siguiente procedimiento: cada uno, partiendo del punto de color $A$, debe recorrer la circunferencia en ambos sentidos (horario y antihorario) y parar cuando encuentren un punto. Pintar de $A$ el segmento determinado por los dos puntos que encontraron y seguir recorriendo la circunferencia hasta encontrar otros dos puntos, pintarlos y continuar haciendo lo mismo. Cuando se crucen en su recorrido deben elegir otro color y volver a empezar el procedimiento, hasta que ya hallan elegido todos los colores, cuando la figura va estar completamente coloreada.

Notemos que con este procedimiento no van a coincidir $2$ segmentos que deban pintarse de diferente color, ya que si esto ocurriera la cantidade de puntos a ambos lados del segmento determinado por los puntos de estos dos colores serían la mismas por lo que la suma de todos los puntos sería par.

Los siguientes son ejemplos de como quedarían las figuras para $n=3,~5,~7$:
n=1.png
N=5.png
N=7.png
Concluimos que los únicos valores de $n$ para los que siempre gana Miguel son con $n$ par.
No tienes los permisos requeridos para ver los archivos adjuntos a este mensaje.
"La suma de las raíces cuadradas de dos lados de un triángulo isósceles es igual a la raíz cuadrada del lado restante."
Responder