El principio de encasillamiento y un profesor que sabe $9$ bromas y cuentos $3$ chistes por conferencia

Question

Un profesor sabe $9$ bromas y cuentos $3$ chistes por conferencia. Demostrar que en un curso de $13$ conferencias habrá un par de chistes que se contarán juntos en al menos $2$ conferencias.

He empezado contando cuántas posibilidades hay de contar chistes en una conferencia. Dejemos que

$$J := \{1,2,\dots,9\}$$

La cantidad de todas las combinaciones posibles de chistes es $9 \choose 3$ y para cada conferencia habrá $3$ pares de chistes únicos $\left(\frac{3!}{2!}=3\right)$ .

No estoy seguro de cómo continuar desde aquí para llegar al PHP, creo que puedo estar haciendo algo mal aquí, ¿algún consejo de cómo abstraerlo correctamente?

---

Este es un ejercicio de la preparación de la prueba de acceso a la Universidad de Tel-Aviv y todavía no soy estudiante, así que la combinatoria elemental debería servir aquí.

Answer 1

Voy a suponer que no cuenta el mismo chiste dos (o tres) veces en la misma conferencia. Si no, he aquí un contraejemplo:

Dejemos que $\{a_1, \ldots, a_9\}$ sea el conjunto de chistes. En el $i$ -día para $1 \leq i \leq 9$ , contar chistes $(a_i, a_i, a_i)$ . Entonces, diga $(a_1, a_2, a_3)$ , $(a_4, a_5, a_6)$ , $(a_7, a_8, a_9)$ y $(a_1, a_4, a_7)$ .

Así que, ahora hacia el ejercicio. Cada día el profesor dice $3$ pares de chistes distintos. Lo que significa que en total cuenta $39$ pares de bromas sobre el $13$ días. Hay $\frac{9!}{7!2!}= 36$ pares de chistes que puede contar. Así que debe contar al menos un par de chistes dos veces.

Answer 2

Obsérvese que hay $\binom{9}{2}=36$ pares de chistes únicos.

En cada conferencia hay tres chistes (A, B y C), por lo que hay tres pares únicos (AB, AC, BC) por conferencia utilizada.

En series de 13 conferencias hay $13*3=39$ pares de chistes usados. Así, tras el principio de encasillamiento, al menos uno de los pares únicos se utiliza al menos dos veces.

Answer 3

A veces es más fácil probar un poco más: Podemos demostrar que el chiste que más veces se ha contado debe estar en el par de chistes que buscamos.

Habrá al menos un chiste que se haya contado al menos 5 veces: Hay $13\cdot3$ ranuras para los chistes y si cada chiste se contara como máximo 4 veces, 9 chistes sólo podrían llenar $9\cdot 4$ ranuras, pero $13\cdot 3 > 9\cdot 4$ . (De hecho, lo he calculado: Con 12 días cada chiste se contaría una media de $\frac{12\cdot3}9=\frac{12}3=4$ veces, así que con un día más al menos un chiste tiene que ser contado más de 4 veces).

Ahora bien, si restringimos nuestra atención a sólo los días en que se ha contado ese chiste, entonces de los otros 8 chistes, al menos uno se ha contado dos veces: Tenemos (al menos) $5\cdot2$ ranuras para llenar, y eso es más que $8$ .

Answer 4

Dejemos que $a_1,a_2,a_3$ ser los chistes que contó el primer día. Para contar chistes durante 13 días, sin que se le acaben los chistes tiene que contar chistes de forma eficiente.

Así que toma un chiste del primer día y lo repite. Los chistes del segundo día son { $a_1,a_4,a_5$ } ...así el número máximo de días que puede hacer eso es=(9-1)/2=4 días

Ahora arregla $a_2$ repetir el proceso anterior sin incluir $a_1,a_3$ . El número máximo de días que puede hacer es=(9-3)/2=3 días.

Repitiendo esto, obtenemos el número máximo de días que puede permitirse contar el chiste=4+3+2+1=10 días

Answer 5

En cada uno de los $13$ conferencias, el profesor puede elegir entre un total de ${9 \choose 3 } = 84$ diferentes combinaciones de chistes.

Y, en cada una de ellas $84$ combinaciones, hay ${ 3 \choose 2 } = 3$ pares distintos.

Así, en cada una de las $13$ conferencias, hay $84 \times 3 = 252$ diferentes pares de bromas posibles.

Por otro lado, sólo hay ${ 9 \choose 2} = 36$ diferentes pares de chistes que podrían ser elegidos de un total de $9$ bromas.

De ahí que debamos tener repeticiones.

Espero que esto ayude.