Hay $100$ estudiantes en una escuela, y forman clubes de $450$. Cualquier dos clubs con al menos $3$ estudiantes en común y cualquier cinco clubes no más que $1$ estudiantes tienen en común. ¿Debe ser que algunos cuatro clubes tienen en común exactamente $1$ estudiante?
Respuestas
¿Demasiados anuncios?
Enis P. Aginić
Puntos
1129
No estoy completamente seguro de que mi argumento es correcto, pero yo diría que no es posible tener por lo menos 3 estudiantes en común con todos los otros grupos, y en la mayoría de entre 5 grupos.
Si nos fijamos en el tamaño de la $s$ de un club, hay ${s\choose 3}$ combinaciones de 3 miembros. Cualquier otro club debe contener al menos uno de los $s\choose 3$ combinaciones. Por lo tanto, el número promedio de veces en que se produce una combinación entre otros clubes, se $449/{s\choose 3}$. Si este número es estrictamente mayor que 3, debe haber al menos una de las combinaciones que se produce entre 4 otros clubes. Esto contradice el segundo supuesto de que no se cinco clubes de intercambio de más de un miembro. Por lo tanto, $s$ satisface $449/{s\choose 3}>3$. Esto le da a ese $s\geq 11$.
Esto significa que en promedio el número de clubes que una persona participa en al menos $11\cdot 450/100=49,5$. Por lo tanto, hay al menos una persona $p$ participación en al menos el 50 clubes. Considerar estos 50 clubes. Por la segunda hipótesis, ninguna de estas cinco clubes de compartir cualquier otro miembro de $p$. Sin embargo, el número total de otros miembros de estos clubes es, al menos,$10\cdot 50=500$, y hay 99 otras personas. Por lo tanto, al menos uno de estos 99 otras personas debe ocurrir en 5 de los clubes. Esto le da una contradicción.
Andy
Puntos
394
El problema puede ser más fácil de resolver si se observa que si un conjunto de clubes tiene X los estudiantes en común, a continuación, todos los subconjuntos que contienen al menos dos de los clubes tienen al menos X los estudiantes en común. Por ejemplo, si tenemos cinco clubes : a, B, C, D, y E, y tres estudiantes en todos los cinco de estos clubes, a continuación, de los clubes, C, y E, que tienen al menos tres estudiantes en común. Clubes de la B y E tienen al menos tres estudiantes en común.
Puede que no sea claro desde el planteamiento del problema que la O. P. no significa que cada dos club combinación debe tener a tres estudiantes en común. Hay ${450*449\over 2} = 101025$ dos club combinaciones de 450 clubes que se forma fuera de los 100 estudiantes parámetro que estamos limitados. Buscando en el mayor club de combinaciones sólo empeora las cosas. Hay ${450*449*448\over 6} = 15086400$ tres combinaciones club
Lo que yo creo que la O. P. quise decir fue que cada uno de los 450 clubes deben tener tres estudiantes en común con al menos otro club y si hay un club que tiene los estudiantes en común con cuatro o más clubes, entonces no puede haber más de un estudiante en común. Teniendo en cuenta estos requisitos debe ser un club donde tiene exactamente un estudiante en común con otros tres clubes.
Para proporcionar un ejemplo contrario me debe demostrar que todos los cuatro club combinaciones tienen 0 alumnos en común o debe tener dos o más estudiantes en común, mientras que la satisfacción de las demás condiciones.
Vamos a suponer que cada tres club combinación no tiene ningún estudiante en común, por lo que para solucionar esto podemos dividir los 450 clubes en 225 conjuntos de 2 clubes. Para satisfacer el primer requisito, que cada club debe tener tres estudiantes en común con al menos otro club, ponemos tres estudiantes en cada conjunto donde todos los estudiantes están separados de ambos clubes en sus respectivas conjunto, esto significaría que un mínimo de 675 estudiantes son requeridos.
Supongamos ahora que en lugar de que cada cuatro club combinación no tiene ningún estudiante en común. Para resolver este dividimos el 450 clubes en 150 conjuntos de 3 clubes. Esto requeriría de 450 estudiantes, aplicando el mismo proceso en el párrafo anterior y el uso de la primera observación anterior.
De esto podemos deducir que los clubes más estudiantes a participar en el menor de los estudiantes están obligados a cumplir los requisitos.
Así que si un estudiante está en todas 450 clubes. Luego cada cinco club combinación tiene un estudiante en común. Para proporcionar un ejemplo contrario, la adición de al menos un estudiante en común para cada uno de los cuatro clubes de la combinación de sin la adición de los estudiantes en común a cualquiera de las cinco club combinación, requiere de ${450*449*448*447\over 24}=1685905200$ adicional a los estudiantes.
Veamos un poco alterado versión del problema donde tenemos 20 clubes en lugar de 450 y en lugar de tener 100 estudiantes que sólo quieren encontrar el número mínimo de estudiantes para proporcionar un ejemplo contrario. Manteniendo todos los demás requisitos de la misma. Dividiendo el 20 clubes en cuatro grupos de cinco clubes, donde cada uno de ellos tiene uno de cada cinco estudiantes de los clubes, a continuación, la adición de dos estudiantes de cada uno de los cuatro clubes de la combinación en cada conjunto. Esto requiere (2 estudiantes)(5 cuatro club de combinaciones en cada set)(4 juegos)+(4 estudiantes) = 44 alumnos. Tratando de un segundo caso donde la división de la 20 clubes en cinco grupos de cuatro clubes de modo que cada conjunto de tres estudiantes en todos los clubes por lo que sólo 15 de los estudiantes están obligados a cumplir con los requisitos de la no cuatro club combinación con exactamente un estudiante en común.
Por lo tanto, tiene un estudiante en más de cuatro clubes causa más problemas de los que resuelve. Dividiendo el 450 clubes en 112 grupos de cuatro clubes y un conjunto de dos clubes, tenemos tres estudiantes en cada conjunto en el que están en todos los clubes en sus respectivas establecido, de modo que necesitamos un mínimo de 339 estudiantes a mostrar un contraejemplo. Por lo tanto, debe haber al menos uno de los cuatro clubes combinación con exactamente un estudiante en común, porque los más de los clubes de los estudiantes en el menor de los estudiantes están obligados a proporcionar un ejemplo contrario, a menos que el estudiante esté en cinco o más clubes en el que caso de que el número de alumnos aumenta en gran medida.
