5 matemáticos (digamos A,B,C,D,E) fueron a ver una película. Mientras la veían, cada uno de ellos durmió exactamente dos veces. Para cada par de matemáticos, hay un momento durante la película en el que ambos matemáticos están dormidos. Es decir, hay al menos un momento durante la película en el que tanto A como B (y quizá otros) están dormidos; hay al menos un momento durante la película en el que tanto A como C (y quizá otros) están dormidos; etc. Demuestra que existe un momento en el que 3 de ellos están dormidos.
Respuesta
¿Demasiados anuncios?
Pawel
Puntos
28
Sea $A_1,A_2,B_1,B_2,\ldots,E_1,E_2$ sean los vértices de un grafo $G$ que representa el $10$ siestas. Conecta un borde entre dos siestas cualesquiera si se solapan.
Afirmo que un ciclo en este gráfico representa un momento en el que $3$ o más matemáticos dormían simultáneamente. Supongamos que $v_1,\ldots,v_n$ es un ciclo en $G$ , $n\ge 3$ . Si alguna siesta representada por $v_i$ en este ciclo empezaron y terminaron durante la siesta $v_{i-1}$ o $v_{i+1}$ entonces está claro que las siestas $v_{i-1}$ , $v_i$ et $v_{i+1}$ todos superpuestos. Si ninguna siesta estaba contenida en otra siesta, entonces sin pérdida de generalidad podemos suponer que $v_1$ es la siesta que empezó primero en el ciclo $v_1,\dots,v_n$ . Por nuestra condición, $v_2$ debe terminar después de $v_1$ extremos. Ahora bien $v_n$ debe coincidir con el mapa $v_1$ por las reglas de nuestro grafo, se deduce que las siestas $v_1,v_2$ et $v_n$ todo se solapa al final de la siesta $v_1$ .
Por contradicción, supongamos que no hay ningún momento en el que $3$ o más matemáticos duermen simultáneamente. Entonces nuestro grafo no puede tener ciclos, y por tanto es un árbol. Por lo tanto, tiene como máximo $10-1=9$ bordes, lo que no es suficiente para crear el $\binom{5}{2}=10$ parejas de nappers.
