Rellenar una cuadrícula de 40 x 40 con cuadrados de 3x3

Question

Se supone que debo averiguar el número mínimo de cuadrados de 3x3 que llenarán completamente esta cuadrícula de 40x40 en la que es aceptable la superposición de cuadrados. Además, cada cuadrado de 3x3 debe coincidir con las líneas de la cuadrícula.

Mi procedimiento para hacer un problema como éste es dividir primero 40 entre 3 y obtengo 13,333 .

Entonces digo que me sobran cuadrados de 13 por 13 (3x3) con una fila y una columna. Entonces relleno el espacio vacío restante con 13 cuadrados para una fila, 13 cuadrados para una columna y 1 cuadrado extra para la esquina. Esto hace que mi respuesta sea 196 cuadrados. ¿Es ésta una solución correcta? ¿Existen otras formas mejores o una fórmula general clara para resolver este tipo de problemas?

Answer 1

Indice las casillas en el $40\times 40$ cuadrícula por un par de enteros $(x,y)$ con $1 \le x, y \le 40$ . Llamemos a la plaza $(x,y)$ como $S_{x,y}$ . Consideremos el siguiente subconjunto de cuadrados de la cuadrícula:

$$\mathcal{S} = \big\{\; S_{x,y} : x \equiv 1 \pmod 3, y \equiv 1 \pmod 3\;\big\}$$

Es evidente $\mathcal{S}$ contiene $\lceil \frac{40}{3} \rceil \times \lceil \frac{40}{3} \rceil = 14 \times 14 = 196$ elementos. Elige dos cuadrados cualesquiera $S_{x_1, y_1}$ , $S_{x_2,y_2}$ de $\mathcal{S}$ tenemos

$$x_1 \ne x_2 \implies |x_1 - x_2 | \ge 3 \quad\text{ OR }\quad y_1 \ne y_2 \implies |y_1 - y_2 | \ge 3$$

Esto implica que no podemos encontrar un $3\times 3$ cuadrado que cubren $S_{x_1,y_1}$ y $S_{x_2,y_2}$ al mismo tiempo.

Si cubrimos la cuadrícula con algunos números de $3\times 3$ cuadrados. En $3\times 3$ cuadrados que cubren elementos distintos de $\mathcal{S}$ son distintos. Esto implica que necesitamos al menos $196$ $3\times 3$ cuadrados para cubrir toda la cuadrícula.

Está claro cómo cubrir el $40 \times 40$ cuadrícula por 196 ejemplares de $3\times 3$ cuadrados. Así que la respuesta deseada es efectivamente $196$ .

La idea básica no difiere de un problema mucho más simple de cubrir un $3\times 3$ tablero de ajedrez blanco y negro con 5 casillas blancas y 4 negras utilizando $1 \times 2$ dominó. Puesto que cada ficha de dominó cubre una casilla blanca y una negra. Si el tablero de ajedrez tiene 5 casillas blancas, necesita al menos $5$ dominó para cubrirlo.

Answer 2

He aquí una solución (al problema tal como se publicó originalmente) que sólo necesita 192 cuadrados:

Rellena la cuadrícula desde arriba a la derecha hasta que hayas colocado 169 cuadrados, dejando sólo un gnomon en forma de L de anchura 1. A continuación, tapa el gnomon como se muestra en el diagrama.

Distancia $AB$ $=\frac14(5\sqrt{17}-9) > 2.9$

Distancia $BC$ $=\frac98(\sqrt{17}-1) > 3.5$

Así que $3 + AB+10BC > 40$ y podemos cubrir el gnomon con 23 cuadrados.

(Obsérvese que la posición del cuadrado que contiene $A$ y $B$ no es óptimo $-$ podemos hacerlo fraccionalmente mejor girándolo en el sentido de las agujas del reloj alrededor de $B$ que nos permite deslizarlo un poco hacia la derecha. Pero esto no sería suficiente para reducir el número total de cuadrados necesarios).

Answer 3

Se puede demostrar en general que si se trata de cubrir un $M\times N$ rejilla con $k\times k$ cuadrados (con $k\le M,N$ ), se necesita al menos

$$\lceil{M\over k}\rceil\lceil{N\over k}\rceil$$

de la $k\times k$ cuadrados, donde $\lceil x\rceil$ rondas $x$ hasta el número entero más próximo. La demostración es básicamente por inducción: Para cubrir el $N$ celdas de la cuadrícula a lo largo de la fila superior, tiene que utilizar al menos $\lceil{N\over k}\rceil$ copias del $k\times k$ cuadrado. Sea como sea que cubras la fila superior, te queda un $(M-k)\times N$ cuadrícula a cubrir.