Probabilístico enfoque a un problema de combinatoria

Question

Problema: En la Duma, hay 1600 delegados, que han formado 16000 comités de 80 personas cada uno. Demostrar que uno puede encontrar dos comités que tengan menos de cuatro miembros comunes.

Hay un probabilística de la solución a esta pregunta, que estoy teniendo problemas para seguir porque yo no tengo de fondo en la probabilidad. Se comienza por calcular el número esperado de común de los miembros de cualquiera de los dos comités y usar esto para encontrar la solución. ¿Cómo funciona esto exactamente?

También estoy interesado en saber si alguien tiene un no-probabilística de la solución.

Fuente: http://www.math.cmu.edu/~ploh/docs/matemáticas/mop2011/prob-método.pdf

EDIT: Después de buscar más, he encontrado la solución trabajado en detalle en la página 2 aquí: http://www.math.cmu.edu/~ploh/docs/matemáticas/mop2010/prob-peine-soln.pdf

Answer 1

Usted puede presentar el mismo problema con un solo $800$ en lugar de $16000$ comités:

Hay $16000\cdot 80$ comité de membresías, por lo tanto, por el pigeon-hole principio, al menos una de las delegaciones $A$ es en, al menos, $800$ comités. (Sólo con $800$ comités, podríamos concluir que $A$ $40$ comités, pero que es suficiente para el cálculo de abajo).

Suponer que no hay comités con cuatro o más miembros comunes que existen. A continuación, dos de $A$'s de los comités tienen en la mayoría de los otros dos delegados en común. Por lo tanto $A$'s de la primera comisión nos da $79$ adicional de los delegados, el segundo en menos $79-2$ adicional de los delegados, ..., el $n$th comité, al menos, $79-2(n-1)$ delegados adicionales (por anteriores del comité, en la mayoría de los dos delegados que ya puede ser "conocido"). Por lo tanto $40$ $A$'s de los comités de contener $$40\cdot 79-(0+2+4+\cdots+78)=1600$$ los delegados aparte de $A$. Pero entonces tendríamos $1601$ delegados, incluyendo a $A$!