Problema 5 Nivel 2 Mayo 2019

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

Colaborador OFO - Medalla de Plata OFO - Medalla de Oro FOFO Pascua 2019 - Medalla
Mensajes: 312
Registrado: Lun 28 Nov, 2011 11:39 am
Medallas: 4
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?

BrunZo

OFO - Medalla de Bronce FOFO 8 años - Mención Especial OFO - Medalla de Plata FOFO Pascua 2019 - Medalla FOFO 9 años - Medalla Especial
Mensajes: 208
Registrado: Mar 21 Nov, 2017 8:12 pm
Medallas: 5
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