P2. IMO 2014 - Configuraciones pacíficas en un tablero

Enviado por jesus el 9 de Julio de 2014 - 11:13.

Sea $n \geq 2$ un entero. Consideremos un tablero de tamaño $n \times n$ formado por $n^2$ cuadrados unitarios. Una configuración de $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 $k$ tal que, para cada configuración pacífica de $n$ fichas, existe un cuadrado de tamaño $k \times k$ sin fichas en sus $k^2$ cuadrados unitarios.

Sugerencia

Sugerencia:

Intenta algunos casos particulares para reconocer algún patrón, por ejemplo, para $n=3, k=1; n=4, k=1; n=5, k=2; n=6, k=2; n=7, k=2; n=8, k=?$ etcétera
Observa que si para algun n, digamos $n = n_0$, encuentras una configuración de fichas tal que no existen cuadrados de tamaño $k_0 \times k_0$ entonces, el valor de $k$ para cualquier $n \leq n_0$ debe satisfacer que $k < k_0$.
De manera dual. Si demuestras que para cualquier configufación pacíficia de un tablero de $n_1 \times n_1$ siempre existe un cuadrado $k_1 \times k_1$ sin fichas, entonces, para cualquier entero $n \geq n_1$ su valor de $k$ debe satisfacer que $k \geq k_1$.
Demuestra que para cualquier cuadrado de tamaño $m^2 \times m^2$ existe una configuración pacífica donde todo cuadrado de $m \times m$ tiene una ficha.
Demuestra que para toda configuración pacífica de un cuadrado de tamañao $(m^2 +1) \times (m^2 +1)$ existe un cuadrado de $m \times m$ sin fichas.
Concluye a partir de los puntos 2 al 5 que todo cuadrado de tamaño $n$ con $m^2<n \leq (m+1)^2$ satisface que su $k$ es exactamente $m$.