Rusia (2000) concurso:Demostrar la existencia de un par de filas y columnas con las intersecciones de diferente color

Question

Tenemos una $100\times100$ directorio dividido en $10^4$ unidad de plazas. Estas plazas son coloreado con cuatro colores de modo que cada fila y cada columna tiene $25$ plazas de cada color. Demostrar que no se $2$ filas y $2$ columnas de tal manera que su $4$ intersecciones están pintadas con diferentes colores.

Mi intento:

Por primera vez me contó el número de pares de $\mathcal P$ $(r_1,r_2)$ tal que $r_1,r_2$ pertenece a la misma fila, pero se diferencian en el color. Esto se puede hacer en $$\binom 42\times25\times 25$$ ways. So, in $100$ rows, this number is $$100\times\binom 42\times25\times 25$$ Now, we can find a pair of columns in $$\binom{100}2$$ maneras.

Así, por el Principio del Palomar, podemos encontrar al menos un par de columnas que contiene $$\left\lceil\frac{100\times\binom 42\times25\times 25}{\binom{100}2}\right\rceil\\=\left\lceil\frac{100\times75\times 50}{50\times99}\right\rceil\\=76$$ of those pairs $\mathcal P$.

---

Pero no puede continuar más. Y este acercamiento también parece engañosa, debido a que en cada par de columnas, siempre podemos encontrar $\binom42\times25\times25$ pares de $\mathcal P$. Así, este enfoque no tiene sentido, creo.

¿Cuál debería ser el enfoque correcto? Y también, "si nos vierta $nk+1$ objetos en $n$ urnas, entonces hay una urna con $k+1$ objetos", este concepto puede ser enchufado en esta pregunta?

Answer 1

Deje que los colores utilizados se $A$, $B$, $C$, $D$. Llamamos a una desordenada par de plazas neoliberal si las dos plazas se encuentran en la misma fila y son de diferentes colores. Cada fila da lugar a $6 \cdot 25^2$ neoliberal pares (dado por $\binom{4}{2}$ posibles pares de colores y $25$ de los cuadrados de cada color). Por lo tanto, lo que se suma sobre todas las filas, hay un total de $100 \cdot 6 \cdot 25^2$ neoliberal pares. Por otro lado, cada par es simplemente la intersección de una fila con un par de columnas distintas. Porque hay$$\binom{100}{2} = 100 \cdot 99/2$$pairs of columns, some pair of columns contains at least$${{100 \cdot 6 \cdot 25^2}\over{100 \cdot 99/2}} = {{2 \cdot 6 \cdot 25^2}\over{99}} > {{12 \cdot 25^2}\over{4 \cdot 25}} = 75$$neoliberal pairs. Thus, some two fixed columns form neoliberal pairs in at least $76$ rows. We henceforth ignore all other rows and columns; we may as well assume that we have only a $76 \veces 2$ board colored in four colors, in which each row contains two different colors and no color occurs more than $25$ veces en cada columna.

Para cada fila, considere la posibilidad de que el par de colores que contiene. Si los pares $\{A, B\}$ $\{C, D\}$ cada ocurrir en algunos de fila, que se hacen; de la misma manera para $\{A, C\}$, $\{B, D\}$ y $\{A, D\}$, $\{B, C\}$. Por lo tanto, supongamos que en la mayoría de un par de colores de cada uno de estos tres conjuntos se produce; ahora buscamos una posible reetiquetado de colores: $\{A, B\}$, $\{A, C\}$, $\{A, D\}$ son los únicos pares que puede ocurrir, o $\{A, B\}$, $\{A, C\}$, $\{B, C\}$ son. En el primer caso, cada una de las $76$ filas contiene un cuadrado de color $A$, lo que implica que una columna tiene más de $25$ plazas de color $A$, una contradicción. En el segundo caso, cada columna puede contener sólo las letras $A$, $B$, $C$. No sólo puede ser $25$ de los cuadrados de cada color $A$, $B$, $C$ en cada columna, para un total de más de $150$ plazas, pero hay $152$ plazas en total, una contradicción. Esto completa la prueba.

Answer 2

Usted ya ha demostrado la existencia de una columna de par tal que $76$ de sus filas contiene los diferentes colores de la plaza de pares. Cuatro diferentes cuadros de colores que estás buscando es, en realidad, en esta columna-par:

El número de los colores como $0$, $1$, $2$ y $3$. Mencionada $76$ filas sólo puede tener seis pares diferentes: $A=\{0,1\}$, $A'=\{2,3\}$, $B=\{0,2\}$, $B'=\{1,3\}$, $C=\{0,3\}$ y $C'=\{1,2\}$. No asumimos ninguna de las letras que figuran en esta columna-par con su pareja; es decir, $A$ y $A'$, $B$ y $B'$, $C$ y $C'$ no pertenecen juntos en esta columna-par (de lo contrario no hay nada que probar). Desde allí se $152$ de las plazas y de un color sólo puede aparecer máximo $50$ veces en esta columna-par, por el principio del palomar, cada color debe existir en esta columna-par. Sin embargo, esto significa que, uno de color debe existir en todas las filas: Por ejemplo: Si la columna de par contiene $A$$B$, debe contener $C$ (debido a que sólo $C$ incluye color $3$), haciendo que el color de $0$ aparecen en todas las filas; si la columna de par contiene $A$$B'$, debe contener $C'$ (debido a que sólo $C'$ incluye color $2$), haciendo que el color de $1$ aparecen en todas las filas. Por lo tanto, uno de color aparece $76$ veces, lo cual es una contradicción.