Demostrando el límite inferior de las ocurrencias de filas/columnas de números en una cuadrícula de n elementos en 2D

Question

Necesito resolver el siguiente problema:

Dado un grid de números de $n \times n$ desde $1$ hasta $n$ donde cada número aparece en el grid exactamente $n$ veces, demuestra que existe una fila o columna que contiene al menos $\sqrt{n}$ números diferentes.

He intentado encontrar la solución y he encontrado la posible solución pero no logro llegar al paso de tomar $2\sqrt{n}$ como límite inferior para el número de ocurrencias de cualquier número $i$ en filas/columnas.

Tengo la intuición de que la solución puede involucrar un método probabilístico ingenuo, aunque para ser honesto realmente no entiendo muy bien este concepto. ¿Puedes señalarme una solución o pistas sobre este problema?

Answer 1

El argumento sobre Problem Solving Art, elaborado, es el siguiente.

Tomemos un valor $k$ entre $1$ y $n$. Si hay $a_k$ filas diferentes y $b_k$ columnas diferentes que contienen el valor $k$, entonces hay $a_kb_k$ celdas totales en la cuadrícula donde puede haber un $k$: todas las intersecciones de estas filas con estas columnas.

Dado que el valor $k$ ocurre exactamente $n$ veces, debemos tener $a_kb_k \ge n$. Por la desigualdad AM-GM, $\frac{a_k+b_k}{2} \ge \sqrt{a_kb_k}$, que se puede aplicar aquí para concluir que $a_k+b_k \ge 2\sqrt n$.

Numeremos las $n$ filas y las $n$ columnas (colectivamente, "líneas") como $1, 2, \dots, 2n$ y sea $d_i$ el número de valores distintos contenidos en la línea $i$. Tenemos $$ \sum_{i=1}^{2n} d_i = \sum_{k=1}^n (a_k + b_k) $$ porque ambos lados están contando lo mismo de dos maneras diferentes: el número de pares $(i, k)$ donde la línea $i$ contiene el valor $k$. El lado derecho de esta ecuación suma $n$ términos que son cada uno al menos $2 \sqrt n$, por lo que concluimos que $$ \sum_{i=1}^{2n} d_i \ge 2 n \sqrt n $$ y, por lo tanto, el valor promedio de $d_i$ es $$ \frac1{2n} \sum_{i=1}^{2n} d_i \ge \sqrt n. $$ Debe haber alguna línea $i$ para la cual $d_i$ sea al menos el promedio, y por lo tanto alguna línea $i$ que contenga $\sqrt n$ valores distintos.