Ibero 2004 - P1

Avatar de Usuario
Gianni De Rico

FOFO 7 años - Mención Especial
Mensajes: 760
Registrado: Vie 16 Sep, 2016 6:58 pm
Medallas: 1
Nivel: Exolímpico
Ubicación: Rosario
Contactar:

Ibero 2004 - P1

Mensaje sin leer por Gianni De Rico » Sab 04 Ago, 2018 10:21 pm

En un tablero de $1001\times 1001$ se pintan algunas casillas de modo que cumplan las siguientes condiciones:
a) Si $2$ casillas son adyacentes, al menos una de ellas está pintada.
b) Si $6$ casillas son consecutivas en una fila o columna, al menos dos casillas adyacentes de ese grupo de casillas están pintadas.

Hallar el menor número de casillas pintadas que puede haber en el tablero.
[math]

Avatar de Usuario
Gianni De Rico

FOFO 7 años - Mención Especial
Mensajes: 760
Registrado: Vie 16 Sep, 2016 6:58 pm
Medallas: 1
Nivel: Exolímpico
Ubicación: Rosario
Contactar:

Re: Ibero 2004 - P1

Mensaje sin leer por Gianni De Rico » Sab 04 Ago, 2018 10:46 pm

Spoiler: mostrar
Sea $n=5k+1$, veamos que el mínimo es $\frac{3}{5}(n^2-1)$. Veamos que cada tira de $5$ tiene al menos $3$ casillas pintadas, en efecto, si el bloque no está sobre una esquina entonces está completamente contenido en dos tiras de $6$ y posee al menos dos casillas pintadas, por lo que si no posee dos casillas adyacentes pintadas entonces estas deben estar en sus extremos, luego, quedan $3$ casillas consecutivas sin pintar en el centro, de donde al menos una debe estar pintada. Si posee dos casillas adyacentes, al menos dos de las otras tres deben ser adyacentes, por lo que una de ellas está pintada. Si el bloque está sobre una esquina, pertenece a una única tira de $6$, por lo que posee dos casillas adyacentes pintadas, y estamos en el caso anterior.
Luego, si retiramos una esquina podemos dividir el tablero en tiras de $5$ disjuntas de la siguiente forma: Separamos la primer columna, nos queda un tablero de $(5k+1)\times (5k)$ y dividimos cada fila en tiras de $5$ disjuntas. En la primer columna, separamos la primer casilla, nos queda un tablero de $(5k)\times 1$ y lo dividimos en tiras de $5$ disjuntas.
Por lo tanto, necesitamos pintar al menos $\frac{3}{5}(n^2-1)$ casillas.

Veamos que este número es alcanzable, y por lo tanto es el mínimo.
Ibero 2004 P1.png

Esta coloración cumple las condiciones del enunciado y pinta $3$ casillas por cada una de las tiras de $5$ disjuntas que armamos antes. Luego, pinta exactamente $\frac{3}{5}(n^2-1)$ casillas. Por lo tanto, el mínimo es $\frac{3}{5}(n^2-1)$.
En particular para $n=1001$ el mínimo es $\frac{3}{5}(1001^2-1)=601200$.
No tienes los permisos requeridos para ver los archivos adjuntos a este mensaje.
[math]

Responder