viernes, 10 de junio de 2011
Problema del 10 de junio (Daniel)
Se marcan algunas casillas de un tablero de $(n^2+n+1)$x$(n^2+n+1)$. Si no hay cuatro casillas marcadas que formen un rectángulo de lados paralelos a los de la cuadrícula, demostrar que el número de casillas marcadas no excede $(n+1)$x$(n^2+n+1)$.
Suscribirse a:
Comentarios de la entrada (Atom)
4 comentarios:
Numeramos las columnas con $1,2,\ldots, n^2+n+1$, cada una con $c_1,c_2,\ldots,c_{n^2+n+1}$ y el promedio de esos numeros sea $C$.
Queremos demostrar que $C\leq n+1$.
A cada fila le asignaremos pares no ordenados de columnas, de tal forma que si el par $(a,b)$ de columna esta asignado a $k$, es porque las intersecciones de $k$ y $a$ y $k$ y $b$ estan marcadas.
Si dos filas distintas tienen asignado el mismo par, entonces hay un rectangulo. Notemos que la función $\binom{x}{2}$ convexa en $\mathbb{R}$ y creciente a partir de $\frac{1}{2}$. Entonces
$$\binom{n^2+n+1}{2}\geq \sum_{i=1}^{n^2+n+1} \binom{c_i}{2}\geq (n^2+n+1)\binom{C}{2}$$
La primera desigualdad por casillas, porque todas las filas tienen pares de columnas diferentes, y la segunda por Jensen. Dividiendo entre $n^2+n+1$
$$\binom{n+1}{2}\geq \binom{C}{2}\Rightarrow n+1\geq C$$.
Porque $n+1,C\geq 1$, asi que como $\binom{x}{2}$ es creciente a partir de $\frac{1}{2}$, se cumple. QED.
(si una imagen se sale del comentario, hagan clic derecho y seleccionen "abrir imagen en nueva pestaña/ventana")
Mi solucion es parecida, solo que pruebo la cota con una Media cuadratica-aritmetica y una ecuacion cuadratica, en vez de usar jensen.
Bien, mi solución es basicamente igual a la de Diego
Yo también usé media cuadrática-aritmética.
Publicar un comentario