Otra pregunta del principio de encasillamiento

Question

Hoy tengo otra pregunta para ti:

Un curso tiene siete temas optativos, y los estudiantes deben completar exactamente tres de ellos para aprobar el curso. Si 200 estudiantes aprobaron el curso, demuestre que al menos 6 de ellos deben haber completado los mismos temas optativos entre sí.

Ahora sé que esto está relacionado con el conteo y el principio de encasillamiento, y hay un par de otras preguntas relacionadas ya planteadas pero no pude aplicarlas a mi pregunta.

Sé que el principio de encasillamiento (informal) establece que si tienes $n$ cajas, y tiene más de $n$ palomas para distribuir entre esos palcos, entonces al menos uno de los palcos contendrá más de una paloma, pero no estoy seguro de cuáles son mis palcos y cuáles son mis palomas en este problema

Answer 1

En lugar de pensar en palomas que hay que meter en cajas, se podría enfocar como lo hace Edsger Dijkstra en http://www.cs.utexas.edu/users/EWD/transcriptions/EWD10xx/EWD1094.html

En concreto, reafirma el principio de la siguiente manera

Para una bolsa no vacía y finita de números reales, el máximo es al menos la media (y el mínimo es como mucho la media).

Se trata de una simple generalización del principio conocido. En su caso, dejemos que las bolsas sean el número de selecciones posibles de 3 optativas de 7 = $\binom{7}{3}$ =35.

Cada bolsa va a recibir un número determinado de estudiantes. El número de alumnos es siempre un número entero $\geq 0$ .

La media es de 200/35 = 5,72 alumnos por bolsa de media. El máximo del conjunto de 35 bolsas debe ser superior a esta media, es decir, al menos 6 de los alumnos deben haber realizado el mismo conjunto de 3 optativas.

Answer 2

En primer lugar, contemos el número de opciones temáticas. Hay 7 cursos y un estudiante debe elegir 3 entre ellos. Por lo tanto, hay $$ {7 \choose 3} = 35$$ tales opciones.

Ahora hay 200 estudiantes. Supongamos que hay como máximo 5 alumnos que han cursado las mismas asignaturas optativas. Tenemos $$5\times 35 =175.$$ Pero $175<200$ y, por lo tanto, al menos 6 estudiantes han cursado las mismas asignaturas optativas.

Answer 3

A menudo es útil en los problemas de tipo encasillado para tratar de hacerlos no trabajo, y cuando ves que no puedes, a menudo ves por qué no puedes.

Por ejemplo, si digo que hay 2 asignaturas optativas y 9 estudiantes, ¿puede ver que al menos 5 estudiantes deben seleccionar la misma asignatura optativa? Sí, porque si se trata de evitar Poniendo 5 alumnos en una optativa, acabas con 4 en cada una y sobra 1.

Ahora aplique este mismo enfoque a su problema. Primero pregunte qué son las "palomas" y qué son los "agujeros". El truco aquí es que tienes que demostrar que al menos 6 estudiantes toman exactamente el mismo conjunto de asignaturas optativas. ¿De cuántas maneras puedes enumerar 3 de 7? Esos son tus agujeros. Ahora tienes 200 palomas para colocar. Ve.

Answer 4

Observe la forma generalizada del principio de encasillamiento: si se colocan más elementos que mr en r clases, entonces al menos una clase contiene más elementos que m. (Puedes demostrarlo por contradicción, o simplemente pensarlo intuitivamente. También el principio de encasillamiento normal se sigue tomando m=1).

Ahora bien, aquí tenemos r=35 clases (como $\tbinom{7}{3}=35$ ) y más de 35*5=175 alumnos están metidos en ellas. El resultado es el siguiente (sea m=5)

Answer 5

En primer lugar, debemos señalar que hay un total de $7 \choose 3$ opciones que los estudiantes pueden tomar. Hay un formulario de opciones en el que pueden marcar una de las 35 casillas.

Ahora 200 estudiantes marcarán estas casillas. Utilizando el principio de los casilleros. Hay 200 palomas y 35 casilleros. Espero que esto ayude.