Lindo para colorear problema en un tablero

Question

Supongamos que el color de una $n\times n$ plaza de la tabla con $n$ exactamente con los colores de $n$ los tiempos de cada uno. Demostrar que no es una columna o una fila que contenga, al menos, $\lceil \sqrt n \rceil$ diferentes colores. Un amigo mío me dio este problema y he conseguido resolverlo, pero me gustaría saber si hay una manera más prolija.

Saludos.

Answer 1

Cada color, ya que se utiliza $n$ tiempos, se encuentra en al menos $2\sqrt{n}$ líneas distintas (es decir, filas y columnas). (Si es que se encuentra en $r$ filas y $c$ columnas,$r c \ge n$; por lo tanto $r+c \ge 2\sqrt{n}$.) La adición de estos, el número de los distintos (color, línea) pares es, al menos,$2n\sqrt{n}$. Por el principio del palomar, entonces, al menos uno de los $2n$ líneas debe contener, al menos, $\sqrt{n}$ (y, por tanto, al menos $\left\lceil\sqrt{n}\right\rceil$) de distintos colores.

Answer 2

Aquí hay otra solución que he encontrado: Supongamos que cada columna contiene menos de $\lceil \sqrt n\rceil$ diferentes colores. Entonces eso significa que El número de veces que un color se repite por cada columna es, al menos, $n-\lceil \sqrt n \rceil$ por Lo que el número de veces que un número se repite en columna a través de la placa orificio es de al menos $n^2-n\lceil\sqrt n\rceil$. Tenga en cuenta que si el color aparece 1 en $k_1$ columnas, a continuación, el número de veces que se repite en columna es $n-k_i$ así obtenemos $n^2-\sum_{k=1}^nk_i\leq n^2-n\lceil \sqrt n \rceil\rightarrow\sum_{k=1}^nk_i\geq n\lceil \sqrt n \rceil\ $

En la otra parte tenga en cuenta que el número de veces que el color 1 es repetido por fila es n menos el número de veces que un número se repite en la mayoría dentro de cualquier columna. Nota si el color $1$ se encuentra en $k_1$ columnas, a continuación, la máxima será de, al menos,$\lceil \frac{n}{k_1}\rceil$, por Lo que debemos tener $n^2-\sum_{k=1}^n\lceil \frac{n}{k_1}\rceil\leq n^2-n\lceil \sqrt n \rceil\rightarrow\sum_{k=1}^n\lceil \frac{n}{k_1}\rceil\geq n\lceil \sqrt n \rceil\ $.

Así que debemos solucionar $\sum_{k=1}^nk_i\geq n\lceil \sqrt n \rceil$ $\sum_{k=1}^n\lceil \frac{n}{k_1}\rceil\geq n\lceil \sqrt n \rceil$

Tenga en cuenta que lo de la desigualdad en la izquierda una igualdad que nos ayudaría. Así que vamos a $\sum_{k=1}^nk_i= n\lceil \sqrt n \rceil$.

Estoy perplejo aquí.