Embaldosar un rectángulo de 7x9 con cuadrados de 2x2 y trominos en forma de L

Question

Es posible cubrir un rectángulo de 7x9 utilizando 0 cuadrados de 2x2 y 21 Trominos en forma de L, por ejemplo:

abbcddeef
aabccdeff
gghiijjkk
glhhimjnk
lloppmmnn
qoorpstuu
qqrrssttu

También es posible cubrirlo con 3 cuadrados de 2x2 y 17 Trominos en forma de L, por ejemplo:

aabbccdee
fagbcddee
ffgghhijj
kkllhhiij
kklmmnnoo
ppqrmsnot
pqqrrsstt

Sin embargo, es no posible utilizar más de 3 2x2 cuadrados, es decir, las cuatro combinaciones restantes no funcionan:

• 6 cuadrados de 2x2 y 13 Trominos en L
• 9 cuadrados de 2x2 y 9 Trominos en L
• 12 cuadrados de 2x2 y 5 Trominos en L
• 15 cuadrados de 2x2 y 1 Tromino en L

...al menos esto es lo que conseguí utilizando la fuerza bruta (un simple programa en C basado en el backtracking). Intenté dar una prueba matemática de esto, pero no pude.

Por favor, ayúdenme a encontrar una prueba que explique por qué no se pueden utilizar más de 3 casillas de 2x2. Gracias por su ayuda de antemano.

Answer 1

Esta respuesta (a un problema de mosaico diferente) me dio la idea de utilizar más de 2 colores para colorear el rectángulo de 7x9 (ya he probado la coloración del tablero de ajedrez sin ningún éxito).

He ideado un esquema de coloreado con el que cada cuadrado de 2x2 cubre siempre el mismo número de campos para cada color, independientemente de su posición. Esto se puede lograr utilizando 3 colores (digamos, a , b y c ):

ababababa
bcbcbcbcb
ababababa
bcbcbcbcb
ababababa
bcbcbcbcb
ababababa

El número de campos por color: $a = 20, b = 31, c = 12$ .

Cada cuadrado de 2x2 cubre 1 a -, 2 b - y 1 c -campos. Sea $S$ denotan el número total de cuadrados de 2x2.

Hay 3 grupos de trominos en forma de L:

• Trominos del grupo 1 tapa 1 a -, 1 b - y 1 c -Campos.
• Los trominos del grupo 2 cubren 1 a -, 2 b - y 0 c -Campos.
• Los trominos del grupo 3 cubren 0 a -, 2 b - y 1 c -Campos.

Dejemos que $L$ , $L_1$ , $L_2$ y $L_3$ denotan el número total de L-trominos, y el número de trominos en cada grupo, respectivamente. Se cumplen las siguientes ecuaciones:

\begin {align} L_1 + L_2 & = a - S \\ L_1 + 2L_2 + 2L_3 & = b - 2S \\ L_1 + L_3 & = c - S \end {align}

( Nota: La suma de estas ecuaciones da como resultado

\begin {align} 3(L_1 + L_2 + L_3) & = a + b + c - 4S \\ 3L + 4S & = a + b + c \\ 3L + 4S & = 63 \N - (= 7 \cdot 9) \end {align}

como se esperaba).

La solución para el sistema de ecuaciones anterior:

\begin {align} L_1 & = \frac {2a - b + 2c - 2S}{3} = 11 - \frac {2S}{3} \\ L_2 & = \frac {a + b - 2c - S}{3} = 9 - \frac {S}{3} \\ L_3 & = \frac {-2a + b + c - S}{3} = 1 - \frac {S}{3} \end {align}

Ya se menciona en la pregunta que los únicos valores posibles para $S$ son 0, 3, 6, 9, 12 y 15. Sustituyendo estos valores en las expresiones de $L_1$ , $L_2$ y $L_3$ muestra que mientras ambos $L_1$ y $L_2$ son positivos para todos los $S$ valores, $L_3$ se convierte en negativo para $S > 3$ , lo que significa que nuestro problema de mosaico no puede resolverse utilizando más de 3 cuadrados de 2x2.