Conjuntos de tamaño, al menos, $k$ con la intersección de tamaño en la mayoría de las $1$ fresco problema.

Question

En la OMM a la Escuela cada estudiante va a al menos $k$ clases y dos clases en la mayoría de las $1$ estudiante en común. Probar que existe un conjunto de $k$ clases donde todas las clases tienen la misma cantidad de estudiantes.

Muchas gracias por la lectura. He estado teniendo problemas para encontrar maneras de combinar ambos de los requisitos. He intentado buscar en los estudiantes como conjuntos de clases, las clases como grupos de estudiantes. Traté de ver como varios gráficos en vano. También traté de inducción, pero creo que si funciona nos necesita una simple hipótesis.

Muchas gracias de antemano

Saludos.

Answer 1

Esta es una simple aplicación del principio del palomar. Deje que el grado de una clase de ser el número de estudiantes que tiene. Supongamos que hay $n$ no vacío clases (tenga en cuenta que $n \geq k$ suponiendo que existe al menos un estudiante). Mostramos a continuación que el grado de una clase es en la mayoría de las $(n-1)/(k-1)$. Por el principio del palomar, en algún grado es alcanzado por $n/[(n-1)/(k-1)] > k-1$ no vacío clases.

Sigue límite superior el grado de una clase. Considere la posibilidad de alguna clase de $C$ estudiantes $s_1,\ldots,s_\ell$. Cada estudiante $s_i$ pertenecen al menos a $k-1$ otras clases, y estos son disjuntas entre los estudiantes (de lo contrario, habrá dos clases de disponer de dos estudiantes en común). Llegamos a la conclusión de que $(k-1)\ell\leq n-1$.