Demostrar que podemos dividir un grupo de 90 personas en 3 grupos de 30 personas cada uno para que todos tengan un amigo en el grupo

Question

Demuestra que podemos dividir un grupo de 90 personas en 3 grupos de 30 personas cada uno, de forma que cada uno tenga un amigo en el grupo si cada uno tiene más de 30 amigos. La amistad es una relación simétrica.

Intenté pensar de forma probabilística.

Dividir el grupo arbitrario en 3 partes iguales, por lo que podemos hacerlo en $${1\over 6}{90\choose 30}{60\choose 30}$$ Dejemos que $D_i$ ser un evento $i$ no tiene ningún amigo en el grupo. El número de estos eventos es $$m_i = {1\over 2}{89-d_i\choose 29}{60\choose 30}$$ donde $d_i$ es el número de amigos de $i$ Así que $$m_i\leq {1\over 2}{59\choose 29}{60\choose 30}$$ Ahora tenemos $$P(\bigcup D_i)\leq \sum _{i=1}^{90}P(D_i) \leq 90\cdot {3{59\choose 29}\over {90\choose 60}} <1$$ Así que la probabilidad de que $\bigcup D_i$ no sucede es más que $0$ y hemos terminado.

Answer 1

Sí, esto me parece una aplicación correcta de la unión atada . En particular, ha demostrado que la probabilidad del evento $(\lnot D_1)\lor (\lnot D_2)\lor\cdots\lor (\lnot D_{90})$ es estrictamente menor que $1$ . Se deduce que la probabilidad del evento $\lnot\left((\lnot D_1)\lor (\lnot D_2)\lor\cdots\lor (\lnot D_{90})\right)\iff D_1\land D_2\land\cdots\land D_{90}$ es estrictamente mayor que $0$ . Así, entre el espacio muestral, es decir, el conjunto de todas las particiones del $90$ individuos en tres grupos de igual tamaño, hay al menos uno para el que $D_1\land D_2\land\cdots\land D_{90}$ , según se desee.