Segundo nivel de la Olimpiada de Mayo 2016

Se dirige a una edad de: 14/15 años

¿Cuántas casillas se deben pintar como mínimo en un tablero 5 x 5 de tal modo que en cada fila, en cada columna y en cada cuadrado de 2 x 2 haya al menos una casilla pintada?

La respuesta requiere que se dé una coloración de ejemplo, para mostrar que es posible y explicar de forma clara que es imposible encontrar una coloración válida pintando menos casillas.

Una de las estrategias para saber cómo buscar es dividir el tablero en zonas como las que nos piden (filas, columnas, o cuadrados 2 x 2) para saber dónde tenemos que pintar al menos una de las casillas.

La forma más eficaz es combinar un poco todas las figuras: utilizar cuatro cuadrados 2×2, una fila y una columna. De esta forma, encontramos varias divisiones, y nos centramos en una de ellas para tratar de encontrar una coloración.

Si tenemos en cuenta esta división, podemos pensar que hacen falta como mínimo colorear cinco casillas, una por cada cuadrado y una para pintar una casilla tanto de la fila como de la columna. Sin embargo, veremos que eso es imposible, porque para usar cinco casillas, será necesario que la de la fila y la de la columna ocupe la casilla común (gris), dejando el resto de la fila y de la columna vacía.

Pero como sólo queremos colorear cinco casillas, debe haber una en cada fila y una en cada columna, por lo que en los cuadrados de tamaño 2 sólo una casilla de cada fila debe estar ocupada, y si en uno de los cuadrados de la parte superior (verde y azul) no hay ninguna casilla coloreada de la fila superior, se puede formar un cuadrado 2×2 con estos dos cuadrados de arriba y los dos de la fila superior (amarilla), que sólo tiene coloreada la casilla común. Y en ese cuadrado no habría ninguna casilla coloreada.

Como hemos visto, no puede colorearse usando sólo cinco casillas. Y esto nos da una pista de cuáles son las que tenemos que colorear para nuestro ejemplo con 6. En los cuadrados, no repetir fila ni columna, y en la fila y la columna que está vacía procurar que no se pueda dejar un cuadrado de tamaño 2.

Se puede ver que ningún cuadrado 2×2 queda sin al menos una casilla pintada, y que también están cubiertas las cinco filas y las cinco columnas.

Así que la respuesta es que como mínimo es necesario pintar 6 casillas.