¿es posible dividir $9\times 11$ rectángulo en uno $1\times 3$ rectángulo y N tetrominós?

Question

Hay un rectángulo de tamaño $9\times 11$ . ¿Es posible dividirlo usando 1 tromino y $N$ ¿Tetrominós?

He probado mucho y parece que no es posible, por lo que quiero demostrar que no es posible.

1. Un método tan sencillo como contar el número de casillas, contar sumar/igualar contradicciones - parece que no funciona.
2. Método de coloración. Tal vez esto funcione, pero entonces no hemos encontrado la coloración correcta.

Lo que quiero decir - leí que a veces tales problemas pueden ser probados coloreando cuadrados rectangulares usando algún patrón específico y esto podría dar alguna contradicción generalmente con algo impar/par.

Probamos muchos patrones de coloreado (el más simple fue colorear cuadrados rectangulares en blanco y negro como un tablero de ajedrez, también colorear la primera línea en negro, la segunda en blanco, etc., también probamos otros patrones de coloreado). No hemos encontrado ninguna contradicción que nos ayude a demostrar que esto no es posible.

Sería bueno que alguien sugiriera alguna idea, de cómo proceder con este tipo de problemas.

P.D. Intenté resolver esto junto con mi hijo de 5º grado y ahora estoy tan metido en esto que realmente quiero resolverlo

Answer 1

Aquí está lo que resulta ser la única solución, con la $1 \times 3$ tromino en el centro:

   i\j 1  2  3  4  5  6  7  8  9 10 11 
    1  2  2  2  3  4  4  4  5  6  6  6 
    2 18  2  3  3  3  4  5  5  5  6 23 
    3 18 18  7  7  7  8  9  9  9 23 23 
    4 18 19 21  7  8  8  8  9 22 24 23 
    5 19 19 21 21  1  1  1 22 22 24 24 
    6 20 19 21 10 11 11 11 12 22 24 25 
    7 20 20 10 10 10 11 12 12 12 25 25 
    8 20 13 14 14 14 15 16 16 16 17 25 
    9 13 13 13 14 15 15 15 16 17 17 17 

He utilizado la siguiente formulación de programación lineal entera. Sea $P$ sea el conjunto de poliominós, y sea $T \subset P$ sea el conjunto de $1 \times 3$ trominoes. Tenga en cuenta que $|T| = 9\cdot 9+ 7\cdot 11=158$ y $|P|=|T|+ 2(8\cdot 9+7\cdot 10)= 442$ . Para $i\in\{1,\dots,9\}, j\in\{1,\dots,11\}$ , dejemos que $P_{i,j}\subset P$ sea el subconjunto de poliominós que contienen cuadrados $(i,j)$ . Sea la variable de decisión binaria $x_p$ indican si el poliomino $p\in P$ se utiliza. Las restricciones son: \begin {align} \sum_ {p \in P_{i,j}} x_p &= 1 && \text {para $i\in\{1,\dots,9\}, j\in\{1,\dots,11\}$ } \\ \sum_ {t \in T} x_t &= 1 \\ x_p & \in \{0,1\} && \text {para $p \in P$ } \end {align} La primera restricción obliga a que exactamente un poliominó contenga cuadrados $(i,j)$ . La segunda restricción obliga a utilizar exactamente un tromino.

Answer 2

Aquí hay una imagen que demuestra que es posible.