Sea [math]n \geq 2 un entero. Consideremos un tablero de tamaño [math]n \times n formado por [math]n^2 cuadrados unitarios. Una configuración de [math]n fichas en este tablero se dice que es pacífica si en cada fila y en cada columna hay exactamente una ficha. Halle el mayor entero positivo [math]k tal que, para cada configuración pacífica de [math]n fichas, existe un cuadrado de tamaño [math]k \times k sin fichas en sus [math]k^2 cuadrados unitarios.
We gave you a start so you'd know what to do
You've seen how it works, now it's over to you (...)
For there's so much more to explore! Numberblocks - https://www.youtube.com/watch?v=KzTR72_srTU
El ejemplo es trivial. Para la justificación hay que fijarse en las n-k filas y las n-k columnas que no contienen al cuadrado. como esas n-k filas pueden tener como mucho una ficha y lo mismo con las n-k columnas, entonces 2(n-k)>=n. por lo que n>=2k.
Defino una tira de tamaño [math]f como un conjunto de [math]f filas consecutivas en el tablero.
Digo que una columna está tapada en una tira si la ficha de esa columna está en la tira.
Tomemos una tira de tamaño [math]f < \sqrt{n} que tenga la primer columna tapada (tiene que existir).
Sabemos que tiene que haber exactamente [math]f fichas en la tira (una por fila).
Si en la tira hay [math]f columnas no tapadas, entonces encontramos un cuadrado de [math]f \times f sin fichas en sus [math]f^2 casillas.
Al ser [math]f < \sqrt{n}, siempre se puede encontrar este cuadrado.
IMO2014P2.png
(Ojo, no es necesariamente así como queda, esta imagen es un ejemplo.)
Conclusión: si [math]k^2 < n siempre se puede encontrar un cuadrado de [math]k \times k sin fichas en sus [math]k^2 casillas.
Ahora hay que probar que si [math]k^2 \geq n entonces existe una configuración pacífica de las fichas que no deja huecos de [math]k \times k. Para esto basta con dar la distribución para cada [math]n.
Sea [math]c = \left \lceil \sqrt{n} \right \rceil.
Tomemos un tablero de [math]c^2 \times c^2 y dividámoslo en bloques de [math]c \times c.
En el bloque ([math]x,[math]y) (contando como matemáticos) poner la ficha en la casilla ([math]y,[math]x) del bloque.
Ahora se pone el tablero de [math]n \times n arriba del que marcamos recién. Las fichas que quedan adentro del tablero de [math]n \times n las dejamos ahí. Si faltan cubrir algunas filas/columnas, ponemos fichas donde haga falta.
IMO2014P2(b).png
Si en el grande no se podía encontrar un hueco de [math]c \times c, acá tampoco.
No tienes los permisos requeridos para ver los archivos adjuntos a este mensaje.
Guía de [math]\LaTeX: sirve para escribir ecuaciones como [math]\frac{11}{8}+ x \lfloor \pi \rfloor = 1
Sea [math]p = \lfloor \sqrt{n-1}\rfloor .Veamos que sin importar como esté distribuída la configuración de [math]n fichas, existe un cuadrado de [math]p * p que no tiene ninguna ficha.
Sea [math]m la fila de la ficha que está en la 1er columna. Agarro la fila [math]m y las [math]p-1 filas inferiores o superiores (siempre puedo hacer eso, puesto que [math]2p -1 \leq n (**) )
Nos quedo un conjunto de [math]p filas (tira de [math]p la llamo Caro), y trazamos el sub-tablero de [math]p * (n-1) formado por esas [math]p filas y las [math]n-1 columnas sin contar la primera del tablero.
- Como [math]p^2 < n-1, podemos dividir ese tablero de [math]p * (n-1) en, al menos, [math]p tableritos de [math]p * p.
- En esos [math]p tableros puede haber [math]p-1 fichas a lo sumo (1 por cada fila menos 1 por la ya usada en la fila [math]m ). Por lo tanto en uno de esos tableros de [math]p * p no hay ninguna ficha, demostrando lo pedido.
(**) [math]p < \sqrt{n-1} < \sqrt{n} \Rightarrow n > p^2 > 2p - 1 (lo cuál para todo p, si quieren formalidad se puede aplicar cuadrática) (**)
-- Lo único que falta demostrar es que existe una configuración de [math]p^2 * p^2, tal que no existe un cuadrado de [math]p * p sin ninguna ficha. La configuración es fácil de encontrar, el problema es la demostración, todas las demostraciones que se me ocurren son largas y tediosas, espero el aporte de algún Prillo.
Sea [math]f(n) el mayor entero positivo tal que, para cada configuración pacífica de [math]n fichas, existe un cuadrado de tamaño [math]f(n) \times f(n) sin fichas en sus [math]f(n)^2 cuadrados unitarios. Vamos a demostrar que [math]f(n)=\left \lfloor \sqrt{n-1} \right \rfloor.
[1][math]f(n^{2})\leq n-1
Vamos a demostrar esto construyendo un ejemplo en el cual todo subtablero de [math]n \times n tiene una ficha en al menos una de sus casillas.
Denotamos [math](i,j) a la ficha que se encuentra en la columna [math]i y la fila [math]j. Donde el [math](1,1) es la casilla de más arriba a la izquierda.
Colocaremos las fichas de la siguiente forma: Los números de las columnas de las fichas que están en las primeras [math]n filas son, en orden, los números entre [math]1 y [math]n^{2} que tienen resto [math]1 en la división por [math]n. Es decir, hay fichas en [math](1,n+1), (2,2n+1),...(n,n^{2}-n+1).
Los números de las columnas de las fichas que estan en las segundas [math]n filas son, en orden, los números entre [math]1 y [math]n^{2} que tienen resto [math]2 en la división por [math]n. Es decir, hay fichas en [math](n+1,n+2), (n+2,2n+2),...(2n,n^{2}-n+2). Y así siguiendo.
Aca se muestran [math]n=2, [math]n=3 y [math]n=4:
12022004_1075939425751060_45429545_n.jpg
No nos detendremos en la demostración de que este ejemplo funciona ahora (ya que son muchas cuentas). La veremos al final de la solución.
[2] De un tablero de [math]n\times n existe un subtablero de [math](n-1)\times (n-1) con exactamente [math]n-2 fichas.
Dividamos el tablero de [math]n \times n en una columna de [math]1\times n y un subtablero de [math](n-1) \times n. Existe una fila de alguno de los bordes del subtablero de [math](n-1) \times n que contiene una ficha. Ya que en caso contrario necesitaríamos que la columna que agarramos tenga dos fichas, y eso no puede pasar.
Recortemos la fila que contiene una ficha.
Ahora tenemos [math]3 subtableros; una columna de [math]1\times n, un subtablero de [math](n-1) \times (n-1) y una fila de [math](n-1)\times 1. Como la fila y la columna tenían exactamente una ficha entonces el subtablero de [math](n-1) \times (n-1) tiene [math]n-2 fichas que era lo que quería demostrar.
[3][math]f(n^{2}+1)\geq n
Por [2] existe un subtablero de [math]n^{2} \times n^{2} con [math]n^{2}-1 fichas.
Si dividimos al subtablero de [math]n^{2} \times n^{2} en [math]n^{2} subtableritos de [math]n \times n como hay mas subtableritos que fichas, por palomar al menos un subtablerito de [math]n \times n no tendrá ninguna ficha. Que era lo que queríamos probar.
[4] Digamos que una configuración feliz de [math]n \times n, es una configuración pacifica de [math]n \times n a la que le sacamos una ficha. Sea [math]g(n) el mayor entero tal que, para toda configuración feliz de [math]n \times n, existe un subtablero de [math]g(n) \times g(n) sin ninguna ficha en su interior. Entonces [math]g(n) \geq f(n).
Esto se observa fácilmente ya que inicialmente (antes de sacar una ficha) teníamos al menos un subtablero de [math]f(n) \times f(n) sin ninguna ficha. Y al sacar una ficha ese tablero que teníamos seguirá estando.
[5] [math]f(n) \geq f(n-1)
Por [2] existe un subtablero de [math](n-1) \times (n-1) con [math]n-2 fichas en su interior, es decir, una configuración feliz de [math](n-1) \times (n-1). Sabemos que [math]f(n) \geq g(n-1) porque esta configuración feliz formaba parte del tablero original de [math]n \times n.
Por [4] [math]g(n-1) \geq f(n-1). Entonces podemos concluir [math]f(n) \geq f(n-1) que era lo que queríamos demostrar.
[6] [math]n \geq f((n+1)^{2})\geq f((n+1)^{2}-1)\geq ... \geq f(n^{2}+1)\geq n.
Obtenemos esto juntando [1], [3] y [5].
Partiendo desde [6] obtenemos que, si [math](n+1)^{2}\geq x \geq n^{2}+1 entonces [math]f(x)=n.
Por lo tanto [math]f(x)=\left \lfloor \sqrt{x-1} \right \rfloor. Que era lo que queríamos demostrar.
Para demostrar que el ejemplo funciona veremos que:
No hay [math]3 fichas en el mismo subtablero de [math]n \times n.
La cantidad de subtableros de [math]n \times n en los que aparece cada ficha menos la cantidad de subtableros de [math]n \times n en los que aparecen dos fichas; es la cantidad total de subtableros de [math]n \times n que se pueden elegir de nuestro tablero de [math]n^{2}\times n^{2}.
Esas dos cosas implicarían directamente que el ejemplo funciona, ya que por un lado contamos la cantidad de subtableros que contienen al menos una ficha y por otro lado contamos la cantidad de subtableros que hay. Si vemos que nos dan lo mismo habremos demostrado que el ejemplo funciona.
Dividamos al tablero de [math]n^{2}\times n^{2} en [math]n^{2} subtableros de [math]n \times n.
Digamos que un subtablero de [math]n \times n es lindo si pertenece a esa división.
Por la forma en la que estan elegidas las ubicaciones de las fichas cada subtablero lindo de [math]n \times n tiene exactamente una ficha.
Digamos que dos fichas son vecinas si los subtableros lindos en los que están comparten vértice o lado. Digamos que son vecinas por lado si los subtableros lindos a los que pertenecen comparten lado.
Es claro que no hay un subtablero de [math]n \times n que contenga a dos fichas que no son vecinas.
Dejo como ejercicio para el lector ver que no hay un subtablero de [math]n \times n que contiene dos casillas vecinas por lado. Que solo son vecinas con la que se encuentra en el subtablero de arriba a la derecha y de abajo a la izquierda (y en el caso en el que existe un subtablero de [math]n \times n que las contenga, se encuentran en los extremos de este). Parte directo de la definición de la ubicación de las fichas.
Habiendo visto esto ultimo, es inmediato que no hay [math]3 fichas en el mismo subtablero de [math]n \times n. Ya que tendría que incluir fichas [math]3 de subtableros lindos distintos, que se encuentran en diagonal. Por lo tanto la diagonal del menor subtablero que incluya a las [math]3 sería mas grande que la diagonal del subtablero de [math]n \times n. Ergo no existe ningún subtablero de [math]n \times n que contenga a [math]3 fichas.
Contemos cuantos hay que contienen a [math]2 fichas. Como bien dijimos antes las fichas tenían que estar en los extremos del subtablero de [math]n \times n . Como una estaba arriba a la derecha de la otra entonces la cantidad de subtableros que existen que contienen a [math]2 fichas, está determinado por la cantidad de fichas que existen que tienen una ficha que está en el subtablero lindo de arriba a la derecha. Que es lo mismo que contar la cantidad de subtableros lindos tales que exista el subtablero lindo de arriba a la derecha. Esa cantidad da [math](n-1)^2.
Contemos por un lado en cuantos subtableros están las fichas de los subtableros lindos de las puntas. Dos de ellas están en [math]1, las otras dos están en [math]n^2.
Por otro lado las de los bordes (que no son puntas) suman [math]2n+3n+...+(n-1)n=(\frac{n(n-1)}{2}-1)n. (La que esta en la segunda columna aparece en [math]2n subtableritos, la que esta en la tercera columna aparece en [math]3n subtableritos, etc. Lo mismo con las filas.)
Ahora contemos las del medio. Hay [math](n-2)^2 fichas en los subtableros lindos del medio. Cada una de las cuales aparece en [math]n^2 subtableritos.
Hagamos la cuenta total, que nos dara cuantos subtableritos de [math]n \times n tienen al menos una ficha.
Esta es: [math]2 \times 1 + 2 \times n^2 + 4 \times(\frac{n(n-1)}{2}-1)n +(n-2)^2\times n^2-(n-1)^2= [math]2+2n^2+2n^2(n-1)-4n+(n^{2}-2n)^{2}-n^2+2n-1= [math]1+2n^2+2n^3-2n^2-2n+n^{4}-4n^{3}+4n^{2}-n^{2}= [math]n^{4}-2n^3+3n^{2}-2n+1.
Ahora nos queda ver que esa es la cantidad de subtableritos de [math]n\times n que hay. Podemos contar la cantidad de elecciones que tenemos de la esquina superior izquierda, ya que esto nos determina el subtablero. La podemos elegir de todo el cuadrado de [math](n^{2}-(n-1)) \times (n^{2}-(n-1)) pegado a la esquina superior izquierda. Esas son [math](n^{2}-(n-1))^{2} elecciones posibles.
Ahora nos queda ver que [math](n^{2}-(n-1))^{2} nos da [math]n^{4}-2n^3+3n^{2}-2n+1. [math](n^{2}-n+1))^{2}=(n^{2}-n+1)) \times (n^{2}-n+1))= [math]n^{4}-n^{3}+n^{2}-n^{3}+n^{2}-n+n^{2}-n+1=n^{4}-2n^3+3n^{2}-2n+1.
Como dan lo mismo nuestro ejemplo funciona. FIN.
No tienes los permisos requeridos para ver los archivos adjuntos a este mensaje.
Vamos a demostrar que si $k^2<n$ entonces existe un cuadrado de $k\times k$ sin fichas
Para esto tomemos un subtablero de $k\times n$ en el que haya una ficha en la primera columna
Para poder tapar todos los cuadrados de $k\times k$ tenemos que poner al menos una ficha cada $k$ columnas consecutivas en ese subtablero, es decir, al menos $\frac nk$ fichas
Como $k^2<n$; tenemos que $\frac nk>k$
Entonces tenemos que poner al menos $k+1$ fichas en $k$ filas, lo que por Palomar nos lleva a tener al menos una fila con más de una ficha, lo que es una contradicción
Por lo tanto, si $k^2<n$ siempre tendremos un cuadrado de $k\times k$ sin fichas en su interior