En cada celda de una $n \times n$ tablero de ajedrez, escribimos la cantidad de $1, 2, 3, . . . , n$ in such a way that each number appears exactly $$ n veces. Probar que existe una fila o una columna del tablero que contiene al menos $\sqrt{n}$ distintos números.
Esta pregunta se está muriendo por una prueba por contradicción, pero me parece que no puede mostrar cómo. Cuando he buscado a través de Internet, es la siguiente sugerencia:
Asumir que cada fila y cada columna tiene menos de $\sqrt{n}$ distintos números en . Para cada fila o columna, considerar el número de los distintos números en .
Me siento como un doble conteo está involucrado en el proceso, pero lo que a contar de dos maneras diferentes? También puedo probar la declaración con el método de probabilidades, pero realmente me gustaría aprender el recuento doble enfoque.
Aquí está la otra prueba:
Elegir una al azar fila o columna ($2n$ opciones). Deje $\textbf X$ ser el número de distintas entradas en él. Utilice el indicador de la variable $I_i$, para la existencia de número de $i$ en el bloque: $\textbf X = \sum I_i.$ Claramente, $E[I_i] = P[I_i = 1]$. A continuación, $P[I_i = 1] \geq 2\sqrt n / (2n) = 1/\sqrt n$. El límite inferior se obtiene si todos los $i$ pasa a ser en algunos $\sqrt n$ filo de la plaza de la sub-matriz. Por lo tanto, por la linealidad $\textbf E[X] \geq \sqrt n$. Esto demuestra la existencia.
