47° IMO (2006) - Problema 2

Problemas que aparecen en el Archivo de Enunciados.
Avatar de Usuario
Caro - V3

Colaborador-Varias OFO - Jurado-OFO 2015
Mensajes: 357
Registrado: Sab 16 Oct, 2010 4:20 pm
Medallas: 2
Nivel: Exolímpico

47° IMO (2006) - Problema 2

Mensaje sin leer por Caro - V3 » Jue 23 Dic, 2010 11:53 am

Decimos que una diagonal de un polígono regular P de 2006 lados es un segmento bueno si sus extremos dividen al borde de P en dos partes, cada una de ellas
formada por un número impar de lados. Los lados de P también se consideran segmentos buenos.
Supongamos que P se ha dividido en triángulos trazando 2003 diagonales de modo que ningún par de ellas se corta en el interior de P. Encuentre el máximo número de
triángulos isósceles que puede haber tales que dos de sus lados son segmentos buenos.
Guía de [math]: sirve para escribir ecuaciones como [math]

jujumas

OFO - Mención-OFO 2015 OFO - Medalla de Plata-OFO 2016 FOFO 6 años - Medalla Especial-FOFO 6 años OFO - Oro perfecto-OFO 2017 FOFO Pascua 2017 - Medalla-FOFO Pascua 2017
FOFO 7 años - Medalla Especial-FOFO 7 años OFO - Medalla de Oro-OFO 2018 FOFO 8 años - Jurado-FOFO 8 años OFO - Jurado-OFO 2019 FOFO Pascua 2019 - Jurado-FOFO Pascua 2019
OFO - Jurado-OFO 2020 COFFEE - Jurado-COFFEE Ariel Zylber
Mensajes: 400
Registrado: Dom 26 Oct, 2014 8:30 pm
Medallas: 12
Nivel: Exolímpico

Re: 47° IMO (2006) - Problema 2

Mensaje sin leer por jujumas » Sab 22 Oct, 2016 1:13 am

Mi primer problema de IMO de una dificultad algo más alta. Mi solución es algo larga, pero se me ocurrió rápido y divide al problema en muchas partes de dificultad más baja.

Solución:
Spoiler: mostrar
Dado un polígono regular con una de sus diagonales (que no son lados) trazadas, llamemos polígonos truncados a los dos polígonos que quedan. Llamemos polígono truncado obtuso a todo polígono truncado que cumpla que en el polígono original es menor a la otra parte del polígono al ser realizada la división.

Sea [math] un entero positivo mayor a uno, definamos [math] como el máximo número de triángulos isósceles que puede haber tales que dos de sus segmentos sean segmentos buenos en un polígono regular de [math] lados. Dado un entero [math], vamos a llamar [math] como el máximo número de triángulos isósceles que puede haber tales que dos de sus segmentos sean segmentos buenos en un polígono truncado de [math] lados (se toma el polígono truncado donde más hay). Llamemos [math] a esta misma función aplicada a polígonos truncados obtusos, solo que a estos cuando tienen [math] lados.


Lema 1: [math]

Demostración: Supongamos que tenemos una configuración maximal de trazos en el polígono. Si ningún triangulo tuviese como dos de sus lados a dos lados del polígono original consecutivos, notemos que no todo vértice del polígono cumple que al menos una diagonal del polígono sale de él, ya que en ese caso habría [math] diagonales, y dos se cortarían en el interior. Luego, tomemos un vértice [math] de donde no salga diagonal, y unamos sus dos vértices vecinos, que es claro que no estaban unidos, y es fácil ver que el número de triángulos isósceles buenos aumenta. Luego, la configuración anterior no era maximal, y existen triángulos isósceles buenos con dos lados consecutivos en el polígono. Tomando las dos regiones que este triángulo determina, el máximo número de particiones para el polígono es la suma del máximo para cada región, al no cruzarse las diagonales, de el lema se cumple.


Lema 2: [math]

Demostración: Notemos que el lado más largo de nuestro polígono truncado es malo. Llamemos [math] y [math] a los vértices de este lado. Notemos que por esto ningún triángulo con vértices [math] cumple que [math] es isósceles bueno con [math] o [math], de donde si existiese uno, tendríamos que [math], pero dado que la cantidad de lados es [math], es facil ver que los segmentos [math] y [math] de este triángulo serían malos. Luego, ningún triángulo isósceles bueno usa este segmento, de donde podemos hacer una biyección entre cualquier partición de este polígono en triángulos isósceles buenos y la misma partición en un polígono regular de [math] lados, donde simplemente enumeramos los vértices en cada polígono y suponemos que [math]. Es facil notar que un segmento es bueno en un polígono si y solo si es bueno en el otro, y los segmentos no se cruzan mientras no se cruzen en el otro polígono, y como no hay triángulos isósceles buenos con [math] y [math], la biyección funciona.


Lema 3: [math] o [math]

Demostración: Notemos que si en la división no existe el triángulo isósceles bueno [math] mencionado en el Lema 2, podemos seguir haciendo la biyección aplicada a este Lema. De existir este triángulo, es claro que el polígono truncado queda dividido en tres regiones iguales que las mencionadas en el Lema, de donde al ser el máximo del polígono truncado el máximo de la suma en las tres regiones, estamos.


Lema 4: [math], donde [math], y donde [math] y [math] son impares.

Demostración: Llamaremos en orden desde [math] hasta [math] a los vértices, [math],[math],[math] hasta [math]. Notemos que todo triángulo isósceles bueno en la configuración tiene entonces de vértices [math], [math], [math], donde [math], [math] y [math] están en progresión aritmética de razón impar. Esto sucede porque el polígono es obtuso, de donde si el punto central del triángulo isósceles no fuese el que cumple que los lados con él como vertice son iguales, tendríamos que el que cumpliese sería uno de los que están a los bordes, pero por la definición de obtuso, este punto caería afuera de la región obtusa. Consideremos el triángulo más grande en la configuración maximal, cuyos vértices son [math], [math] y [math]. Notemos que ahora el polígono truncado quedó dividido en cuatro (o menos) polígonos truncados, que van desde [math] hasta [math], [math] hasta [math], [math] hasta [math] y [math] hasta [math]. Llamando estas regiones con números del uno al cuatro en orden, las únicas regiones que podrían compartir ahora lados de un triángulo isósceles bueno son la [math] y la [math], ya que las otras implicarían un cruce de diagonales. Sin embargo, esta unión rompe con la condición de que el triángulo [math] es el más grande. De donde en particular [math] es a lo sumo la suma de las funciones [math] de cada una de estas cuatro regiones, más el triángulo maximal formado.


Lema 5: [math].

Demostración: Esto lo demostraremos por inducción fuerte. Si [math], es fácil checkear que es cierto a mano. Si todos los enteros [math] del [math] al [math] cumplen, queremos ver que [math] y [math] cumplen. Para ver que [math] cumple, usemos el lema [math] que nos dice que [math]. Hagamos reemplazos [math], [math], [math], [math] por las variables, de donde por hipótesis inductiva [math], donde [math]. Viendo los casos donde [math] y [math] son ambos pares o ambos impares, llegamos a concluir que en particular [math], y el ejemplo existe tomando los triángulos [math]; [math], etcétera. Se puede razonar análogamente lo mismo para [math], de donde el paso inductivo esta completo.


Lema 6: [math]

Demostración: Por los Lemas [math], [math] y el Lema [math] llegamos a que [math] o [math]. Recurriremos nuevamente a la inducción para probar este Lema. Es obvio que para [math], el Lema es cierto. Se puede checkear a mano que [math] es [math]. Supongamos ahora que se cumple para [math]. Tenemos que [math]. Luego, para [math], si no tuviésemos que [math], tendríamos que [math], que por el Lema [math] es igual a [math], de donde la desigualdad se cumple y estamos.


Lema 7: [math]

Demostración: Por el Lema [math] y el Lema [math], tenemos que [math]. Luego, para probar la igualdad, simplemente tomamos todos los triángulos de dos lados consecutivos del polígono y es fácil ver que se cumple.

Con este último Lema, podemos concluir entonces que [math] es la respuesta al enunciado.

Responder