Supongamos que 21 niñas y 21 niños participan en un concurso de matemáticas. Muestre que hay una pregunta que fue resuelta por al menos tres niñas y al menos tres niños.

Question

Supongamos que $21$ de las niñas y $21$ niños entrar en un concurso de matemáticas. Además, suponga que cada participante se resuelve en la mayoría de las $6$ preguntas, y por cada niño-niña de la pareja, hay al menos $1$ pregunta que ambos resuelto. Mostrar que no es una cuestión que se ha resuelto por el a $3$ tres niñas y a leat $3$ varones.

Mi pregunta es, ¿por qué es el número de $3$ especial aquí, por ejemplo, traté de probar esta pregunta de la siguiente manera. Revisión de una niña de $g$, esta chica podría haber resuelto en la mayoría de los $6$ preguntas $q_1,\dots,q_6$. Por el bien de la contradicción, asumir Cada pregunta fue resuelta en la mayoría de los 2 chicos o dos chicas. Considerar en primer lugar si no es en la mayoría de las $2$ varones, a continuación, para cada una de las $6$ preguntas $g$ respondió, no podía ser en la mayoría de las $2$ pares que involucran a ella y a $2$ otros muchachos que se ha resuelto esta cuestión, así que para todos los su $6$ preguntas, podría ser en la mayoría de las $12$ pares que involucran a ella y a los otros chicos. Si sumamos a este número sobre todos los $g$, ($21$ en total), obtenemos el número de pares es en la mayoría de las $21\times 6 \times 2=252$. Esto es una contradicción ya que hay $21^2=441$ parejas de chicos, chicas, el segundo caso en la mayoría de los $2$ niñas también pasa lo mismo, por simetría, por lo que en ambos casos tenemos una contradicción.

Mi pregunta: ¿por Qué es el número de $3$ especial aquí? Si hubiera sido reemplazado por $4$, luego de nuestra última ecuación sería $21 \times 6 \times 3=378$, lo que es todavía menos de $441$, me estoy perdiendo algo aquí?

Answer 1

Sabemos que hay al menos $21^2 = 441$ conexiones entre un niño y una niña. Deje $S$ ser el conjunto de conexiones ($|S| \ge 441$). Ahora el color de todas las conexiones con diferentes colores, dependiendo de los problemas. Ahora podemos escribir $S=A \cup B \cup C$, donde en el subconjunto $A$ son las conexiones correspondientes a los problemas que resuelve, en la mayoría de los $2$ de las niñas, en $B$ son las conexiones correspondientes a un problema resuelto por en la mayoría de las $2$ varones y en $C$ son las conexiones correspondientes a un problema resuelto por al menos $3$ de los niños y, al menos, $3$ niñas. Tenga en cuenta que cada uno de conexión debe ser de al menos uno de estos conjuntos y también notemos que el $A$ $B$ no debe ser distinto. Obviamente ahora nuestro objetivo es demostrar que $C \not = \emptyset$.

Así que ahora suponga que $C = \emptyset$ y escoger una al azar niño y como se ha resuelto en la mayoría de las $6$ problemas a los que nos tienen que al menos uno de este problema ha sido resuelto por al menos $3$ niñas. Así que en la mayoría de los $5$ problemas han sido resueltos a la mayoría de los $2$ niñas. Eso significa que cada niño contribuye a una $A$ a la mayoría de los $5 \cdot 2 = 10$ conexiones. Por lo tanto, tenemos que $|A| \le 21 \cdot 10 = 210$. Razonamiento Similar nos da ese $|B| \le 21 \cdot 10 = 210$.

Así que ahora:

$$|S| = |A \cup B \cup C| = |A \cup B| = |A| + |B| - |A \cap B| \le 210 + 210 = 420$$

Pero esto contradice el hecho de que $|S| \ge 441$, lo que significa que nuestra suposición de que $C = \emptyset$ es malo. Por lo tanto, hay una conexión en $C$ correspondiente a un problema resuelto por al menos $3$ de los niños y, al menos, $3$ de las niñas, garantizando la existencia de tal problema.

Answer 2

Una solución elegante que se puede encontrar aquí:

https://books.google.nl/books?id=NWhIDQAAQBAJ&pg=PA123&lpg=PA123&dq=21+girls+21+girls+problem+solved+by+at+most+6&source=bl&ots=URHyJ6yHLq&sig=cLbSr7B-cDqMDff2MGs4_zDqPQc&hl=nl&sa=X&ved=0ahUKEwiE5OW4mvjPAhXEVRoKHdH9Ai4q6aeiotae#v=onepage&q=21%20girls%2021%20girls%20problem%20solved%20by%20at%20most%206&f=false

La idea es la siguiente: Comience por hacer una $21\times 21$ matriz y asignar a cada problema una letra diferente. La entrada $(i,j)$ consiste de letras (problemas) que de niña de las $i$, y el muchacho $j$ ambos resuelto.

Observación 1: En cada fila y en cada columna no aparecerá en la mayoría de los 6 distintas letras.

Observación 2: habrá al menos 11 entradas (cuadrados) en cada fila, que contiene una carta que aparece al menos 3 veces en la fila. Lo mismo vale para cada columna.

El Color de los cuadrados que contienen una letra que aparece al menos 3 veces en la misma fila roja.

El Color de los cuadrados que contienen una carta que aparecer al menos 3 veces en la misma columna azul.

Por una paloma agujero argumento se puede mostrar que hay una plaza que es de color rojo y azul, que muestra que hay un problema que se resuelve por al menos 3 chicas y 3 chicos.

Desde $21^2 < 21\times 11 + 21\times 11$ no debe ser un cuadrado que es de color rojo y azul.