Tenemos $101$ tenorista, cada dos cooperaron en exactamente un concierto, pero no hay ningún concierto en el que todos hayan participado.

Question

Tenemos $101$ tenorista, cada dos cooperaron en exactamente un concierto, pero no hay ningún concierto en el que todos hayan participado. Pruebe que alguien participó en al menos $11$ conciertos.

Este es un viejo problema de la Olimpiada de Matemáticas de Moscú. Traté de resolverlo pero de alguna manera no puedo. ¿Alguna idea?

Lo intenté con la doble contabilidad. Digamos que tenemos $T_1,T_2,...,T_{101}$ tenoristas y $A_1,A_2,...A_n$ concierto. Así que cada pareja $\{T_i,T_j\}$ está "conectado" a un solo concierto. Así que lo hemos hecho:

$$ \sum {deg(A_i) \choose 2} = \sum deg(\{T_i,T_j\}) = {101 \choose 2}\;\;\;\;\;(1)$$

Tenemos que probar que el grado de algunos $T_j$ es por lo menos $11$ . Supongamos que no existe tal $j$ entonces por cada $T_j$ el grado es como mucho $10$ y lo hemos hecho: $$ \sum deg(A_i) = \sum deg(T_i) \leq 1010 \;\;\;\;\;(2)$$

No sé qué hacer ahora.

Answer 1

Tomemos un tenorista arbitrario, digamos $T_1$ . Está involucrado en, como mucho. $10$ conciertos, que lo combinaron una vez con cada uno de los restantes $100$ tenoristas. Por lo tanto, al menos uno de estos conciertos, digamos $A_k$ debe involucrar al menos $11$ tenoristas.

Dado el concierto $A_k$ con la participación de $m \ge11 $ tenoristas, y un tenorista $T_p$ no en $A_k$ para cada tenorista $T_i$ en $A_k$ habrá un concierto único que incluye $T_i$ y $T_p$ . Esto da una lista de $m$ concierto, uno para cada uno $T_i \in A_k$ y todos estos deben ser conciertos distintos, diferentes de $A_k$ ya que no hay dos miembros de $A_k$ puede estar en otro concierto.

Así que, esto da $m \ge11 $ concierto en el que $T_p$ es un miembro.

¿El resultado sería también cierto con un número menor de tenoristas? A menos que me falte algo, mi prueba también debería funcionar si hay $92$ tenoristas.