Mateclubes 2019 - Nivel 4 Problema 3

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: 201
Registrado: Mar 21 Nov, 2017 8:12 pm
Medallas: 5
Nivel: 1

Mateclubes 2019 - Nivel 4 Problema 3

Mensaje sin leer por BrunZo » Dom 01 Dic, 2019 11:16 am

En el club de tenis Mateclubes se disputó un torneo de tenis, en el cual participaron $5$ tenistas. Cada tenista jugó una vez con cada uno de los demás tenistas. Se sabe que cada tenista le ganó a otros $2$ tenistas, y perdió con otros $2$. Decimos que un trío de tenistas $A$, $B$ y $C$ es parejo, si $A$ le ganó a $B$, $B$ le ganó a $C$ y $C$ le ganó a $A$.
  1. Determinar cuántos tríos parejos puede haber en el torneo. Dar todas las posibilidades.
  2. Si en otro torneo participan $101$ tenistas, y cada teniste le gana a $50$ tenistas y pierde con otros $50$ tenistas, cuantos tríos parejos puede haber en el torneo. Dar todas las posibilidades.

Avatar de Usuario
Turko Arias

Colaborador OFO - Medalla de Plata OFO - Medalla de Oro FOFO Pascua 2019 - Medalla
Mensajes: 309
Registrado: Lun 28 Nov, 2011 11:39 am
Medallas: 4
Nivel: Ñandú
Ubicación: La Plata, Provincia de Buenos Aires

Re: Mateclubes 2019 - Nivel 4 Problema 3

Mensaje sin leer por Turko Arias » Lun 02 Dic, 2019 1:23 pm

Lindo lindo problema :D :D :D
Pasemos el problema a algo más concreto (tip copado que sirve en banda de problemas, leer antes de leer la solución)
Spoiler: mostrar
Vamos a representar el problema con un lindo dibujito. Supongamos que tenemos $n$ personas en el torneo que juegan todos contra todos (con $n$ impar), y supongamos que cada persona ganó exactamente $\frac{n-1}{2}$ partidos y perdió los restantes. Cada persona $A_1, A_2, ..., A_n$ va a ser representada como un punto, y cada partida va a ser representada con una flecha de manera tal que si la flecha apunta de $A_i$ a $A_j$ entonces $A_i$ le ganó a $A_j$, y apunta de $A_j$ a $A_i$ si $A_j$ le ganó a $A_i$. Notamos que entre dos puntos siempre hay una y solo una flecha que los une, porque solo juegan una partida, y porque no puede pasar que ambos salgan victoriosos.
El problema nos habla de tríos de tenistas parejos. En nuestro dibujito un trío de tenistas parejos se representa con el siguiente dibujo:
Mateclubes1.jpg
Ahora el problema se vuelve:
Tengo $n$ puntos, y de cada punto salen $\frac{n-1}{2}$ flechas que apuntan a otros puntos, entre dos puntos siempre hay exactamente una flecha. ¿Cuántos triángulos como el de arriba hay en total? Dar todas las posibilidades.
Solución
Spoiler: mostrar
Plot twist:
Spoiler: mostrar
Hay una única posibilidad
mindblown.gif
Notemos lo siguiente, en nuestro dibujo hay UNICAMENTE dos tipos de triángulos:
-Los que forman tríos parejos (con su respectivo dibujo en el spoiler del principio)
-Los que no forman tríos parejos, que son todos los de la pinta
Mateclubes2.jpg
Pero entonces tenemos lo siguiente:
TRIÁNGULOS TOTALES = TRIÁNGULOS PAREJOS + TRIÁNGULOS NO PAREJOS, de donde
TRIÁNGULOS PAREJOS= TRIÁNGULOS TOTALES-TRIÁNGULOS NO PAREJOS

Pero tenemos que la cantidad total de tríangulos no es otra cosa que $\binom{n}{3}$. Calculemos ahora la cantidad de triángulos no parejos, para eso, notamos que en cada triángulo no parejo hay un y exactamente UN punto, del que salen dos flechas. Por lo tanto, contar la cantidad de triángulos no parejos es lo mismo que contar la cantidad de triángulos de los cuales de uno de sus vértices salen dos flechas. Pero observamos que de cada punto salen $\frac{n-1}{2}$ flechas, por lo que la cantidad de maneras de elegir dos de esas flechas es $\binom{(n-1)/2}{2}$, y cada posible elección forma un triángulo no parejo. Iterando este proceso con cada punto, tenemos que la cantidad total de triángulos no parejos es $\binom{(n-1)/2}{2} \times n$. Reemplazando entonces nos queda:
TRIÁNGULOS PAREJOS= $\binom{n}{3} - \binom{(n-1)/2}{2} \times n$.

Para responder cada inciso basta reemplazar $n=5$ y $n=101$ en la fórmula de arriba y estamos 8-) 8-) 8-)
No tienes los permisos requeridos para ver los archivos adjuntos a este mensaje.

Responder