Sea $n$ un entero positivo, y sea $N=n^2+1$. Se tienen $N$ colores, cada cuadrito unitario de una cuadrícula de $N$x$N$ se colorea usando uno de los $N$ colores, de tal manera que cada color fue utilizado exactamente $N$ veces.
Demostrar que existe una columna o una fila en donde hay al menos $n+1$ colores distintos.
5 comentarios:
Creo que este problema venía en un examen del año pasado, pero no general, era con $n$ fijo.
Sean $a_{1},\: a_{2},...,a_{n^{2}+1}$ los $n^{2}+1$ colores.
Sea $f(a_{i})$ el número de columnas y filas en las que aparece el color $a_{i}$. Ahora demostraré que para todo i se cumple que $f(a_{i})\geq2n+1$. Supongamos que no, entonces $\exists$ un acomodo tal que $f(a_{i})\leq2n$, entonces digamos que aparece en k columnas y r filas, entonces el máximo número de cuadros pintados de ese color es kr, pero para hacerlo máximo, consideramos k+r=2n, entonces $kr=(n-s)(n+s)=n^{2}-s^{2}\leq n^{2}$, contradicción, ya que debe aparecer almenos $n^{2}+1$ veces cada color.
De lo anterior que $\sum_{i=1}^{n^{2}+1}f(a_{i})\geq(n^{2}+1)(2n+1)=2n^{3}+n^{2}+2n+1$.
Por otro lado si en cada columna y cada fila hubiera una cantidad menor o igual a n colores distintos, entonces el máximo valor de la suma de colores distintos en cada columna y fila sería $n(2n^{2}+2)=2n^{3}+2n$.
Ahora vemos que $2n^{3}+n^{2}+2n+1>2n^{3}+2n$, por lo cual llegamos a una contradicción, y en alguna columna o fila debe haber almenos $n+1$ colores.
Muy bien!.. mi solución es esencialmente la misma.
Si venia en el primer entrenamiento del año pasado, para n=7 creo. Mi solucion es parecida a la de Manuel
Tambien nos los pusieron en un examen de Morelos pero con $N$ cualquier entero positivo y demostrar que hay al menos raiz de $N$ colores distintos en alguna fila o columna.
Publicar un comentario