Demostrando que hay un elemento común a todos los juegos de $35$ dado cierto establece restricciones a la

Question

Considere la posibilidad de la $35$ conjuntos de $A_1,A_2,\dots,A_{35}$ tal que $|A_i|=27$ para todos los $1\leq i \leq 35$, y cada triplete de conjuntos tiene uno exactamente un elemento en común a los tres. Demostrar que existe al menos un elemento común a todas las $35$ conjuntos.

Este fue un problema que me dio un amigo le pidió que le ayudara con esto, pero soy incapaz de averiguar la respuesta. Él sugiere algo acerca de la contradicción y el principio del palomar, pero no estoy seguro de cómo continuar. Mencionó que era alguna especie de Olimpiada, pero yo no recuerdo que uno (algo oriente medio?)

He encontrado esta pregunta similar en línea: https://artofproblemsolving.com/community/q1h1699161p10908761

pero esto no incluye ningún tipo de restricciones de cardinalidad, y es sólo un caso de un disjuntos a pares conjunto.

Answer 1

Permite asumir que no hay ningún elemento común a todos los 35.

Cualquier conjunto $A_i$ es parte de $\binom{34}{2} = 561$ trillizos. $A_i$ tiene 27 artículos. $ 27 \cdot 20 = 540 < 561 $, por lo que desde el principio del palomar algún punto a de la $A_i$ debe ser en 21 de los trillizos. Esto significa que al menos el 7 otros conjuntos debe incluir, desde el $\binom{7}{2} = 21$. A su vez, esto significa que una es de al menos 8 conjuntos (incluyendo $A_i$). Entre estos conjuntos, hay $\binom{8}{2} = 28$ pares.

Vamos a asumir algunos de $A_j$ no contiene una. $A_j$ debe tener algún elemento en común con cada una de las $28$ pares.

Si un elemento de b es común a $A_j$ y en dos subconjuntos que contienen, no debe estar en cualquier otro subconjunto que contiene, ya que cada triplete sólo tiene un elemento en común, así que no hay tres conjuntos que incluyen una puede compartir el elemento b.

Esto significa que no debe ser de al menos 28 elementos únicos en $A_j$, pero esto es imposible, ya que $|A_j| = 27$.

Por lo que una debe ser común a todos los conjuntos de $A_j$, en contradicción con la hipótesis.