Problema 5 Nivel 2 Mayo 2019

Problemas que aparecen en el Archivo de Enunciados.
Avatar de Usuario
Turko Arias

Colaborador-Varias OFO - Medalla de Plata-OFO 2016 OFO - Medalla de Oro-OFO 2019 FOFO Pascua 2019 - Medalla-FOFO Pascua 2019 COFFEE - Jurado-COFFEE Matías Saucedo
OFO - Jurado-OFO 2020 FOFO Pascua 2020 - Jurado-FOFO Pascua 2020 COFFEE - Jurado-COFFEE Carolina González COFFEE - Jurado-COFFEE Ariel Zylber COFFEE - Jurado-COFFEE Iván Sadofschi
Mensajes: 428
Registrado: Lun 28 Nov, 2011 11:39 am
Medallas: 10
Nivel: Ñandú
Ubicación: La Plata, Provincia de Buenos Aires

Problema 5 Nivel 2 Mayo 2019

Mensaje sin leer por Turko Arias » Vie 26 Jul, 2019 5:12 am

Consideramos los $n$ vértices de un polígono regular de $n$ lados. Se tiene un conjunto de triángulos con vértices en estos $n$ puntos con la propiedad que para cada triángulo del conjunto, al menos uno de sus lados no es lado de ningún otro triángulo del conjunto. ¿Cuál es la mayor cantidad de triángulos que puede tener el conjunto?
Fundamentalista del Aire Acondicionado

BrunZo

OFO - Medalla de Bronce-OFO 2018 FOFO 8 años - Mención Especial-FOFO 8 años OFO - Medalla de Plata-OFO 2019 FOFO Pascua 2019 - Medalla-FOFO Pascua 2019 FOFO 9 años - Medalla Especial-FOFO 9 años
OFO - Medalla de Oro-OFO 2020 FOFO Pascua 2020 - Copa-FOFO Pascua 2020
Mensajes: 269
Registrado: Mar 21 Nov, 2017 8:12 pm
Medallas: 7
Nivel: 1

Re: Problema 5 Nivel 2 Mayo 2019

Mensaje sin leer por BrunZo » Vie 26 Jul, 2019 1:38 pm

Solución:
Spoiler: mostrar
Digo que el máximo es $\binom{n-1}{2}=\frac{(n-1)(n-2)}{2}$. Es fácil ver que se pueden construir $\binom{n-1}{2}$ triángulos, todos con un vértice en común, que cumplen la condición.
Supongamos que hay $t>\binom{n-1}{2}$ triángulos. Supongamos que en cada triángulo tomamos uno de los lados que no pertenezca a ningún otro triángulo, y lo pintamos de rojo. Hay $t$ segmentos rojos. Ahora, pintamos todos los otros segmentos de azul. Hay $\binom{n}{2}-t<\binom{n}{2}-\binom{n-1}{2}=n-1$ segmentos azules.
Como cada triángulo tiene tres lados, hay $2t$ lados que se apoyan sobre un segmento azul (pueden haber varios lados apoyados sobre el mismo segmento). Además, no puede haber más de $n-2$ lados apoyados en el mismo segmento, luego los $2t$ son como mucho $(\binom{n}{2}-t)(n-2)<(n-1)(n-2)$, esto es, $t<\frac{(n-1)(n-2)}{2}=\binom{n-1}{2}$, lo cual contradice la hipótesis, de modo que el problema queda resuelto.

Responder