Mosaico de una $n\times n$ Cuadrícula

Question

Dado un $n\times n$ cuadrícula, y $2\times 2$ baldosas a cuadros (blancos en la parte superior izquierda e inferior derecha de las curvas, y negro en la parte superior derecha e inferior izquierda esquinas), ¿cuál es el menor número de cuadrados de color negro que puede estar mostrando un mosaico que cubre la rejilla (se superpone permitido)?

Las baldosas pueden ser giradas en su colocación, se supone que el ser infinitamente delgada, y se colocan una a una en la parte superior de la cuadrícula/azulejo de configuración, es decir, el icono más reciente que ha sido colocado debe tener las cuatro plazas al descubierto. Las baldosas no sobresalga de los bordes de la cuadrícula, pero debe ser colocado enteramente dentro de la cuadrícula.

He sido capaz de lograr embaldosados de tal manera que sólo $n$ cuadrados negros están mostrando, pero me parece que no puede probar que este es el mínimo (si es que).

Answer 1

Sí, $n$ cuadrados negros es mínima.

No importa cómo usted azulejo de la cuadrícula, siempre habrá al menos un cuadrado negro en cada fila y en cada columna debido a la adición de un nuevo mosaico siempre coloca un cuadrado negro en ambos de las filas y columnas en las que el azulejo se añadió. El lo mejor que puedes hacer es tener una línea negra a lo largo de la diagonal.

Aquí hay una manera de lograrlo: