Número mínimo de casillas azules en un tablero 7x7

Question

Una ayuda en este problema:
En un tablero de 7 × 7 cada casilla se pinta de rojo o azul de tal manera que cualquier casilla del tablero tenga al menos dos casillas vecinas azules. Determine la menor cantidad de casillas azules que puede haber en el tablero.
Dos casillas son vecinas si tienen un lado en común.
Mi avance consiste en haber pintado las casillas tratando de que la mayoría tenga sólo 2 casillas azules vecinas, pero mi problema es:
... ¿cómo se que he conseguido el mínimo?
¿habrá otra configuración con menos casillas azules?
gracias

 

Comments

Muy bonito problema.

Answer 1

El mnimo son 31 casillas azules. Primero probemos que se requiren al menos 31. En el tablero que está abajo, cada grupo de casillas con el mismo número consta de los vecinos de alguna casilla. Por lo tanto, al menos dos de cada grupo de casillas con el mismo número deben ser azules. Eso nos da un total de al menos 28 casillas azules en las casillas numeradas. Finalmente, de las casillas marcadas equis al menos tres deben ser azules: (1) si la del centro es azul, se necesita una más entre las tres equis de arriba (para que la casilla con un 9 rodeado de equis tenga dos vecinos azules) y analogamente una más entre las tres equis de de abajo, (2) si la del centro no es azul, entonces se necesitan al menos 4 equis azules: 2 arriba y dos abajo.

La siguiente coloración muestra que es posible cumplir los requisitos marcando 31 casillas: