Coppia L-tromino!

Question

Amy sta giocando con diversi polyominoes. All'improvviso pensa a un problema come segue.

Scegli due numeri interi positivi $m,n$. Se possiamo usare solo L-trominos per tessellate a$m\times n$ rettangolo senza spazi, sovrapposizioni o qualsiasi quadrato che sporge dai rettangoli, quindi chiamiamo la coppia $(m,n)$ Coppia L-tromino.

Chiama suo fratello Ben e il genio e cerca di capire tutte le coppie di L-tromino. Il genio è super intelligente e li ha trovati tutti con una prova. Puoi?

---

Problema da solo.

---

Ecco una foto di L-tromino, se vuoi vederla:

Answer 1

Ovviamente entrambe le dimensioni di un rettangolo piastrellabile devono essere almeno $2$. Inoltre, poiché l'area di un tromino è$3$, l'area di un rettangolo piastrellabile è un multiplo di $3$e quindi almeno una delle dimensioni è un multiplo di 3.

Prima alcuni semplici casi:

$3k\times2n$: Due tromini formano un $3\times2$rettangolo. Quindi qualsiasi$3k\times2n$ il rettangolo è banalmente piastrellabile.

$6k\times(2n+3)$: Questo rettangolo si divide in un file $6k\times3$ e a $6k\times2n$ rettangolo, entrambi istanze del caso banalmente piastrellabile sopra.

Il caso più complicato è questo:

I casi precedenti si occupano di tutti i rettangoli in cui una delle dimensioni è pari. Quindi ora rimangono solo quelli con dimensioni dispari.

$9\times5$: Questo rettangolo può essere piastrellato:

$(6k+9) \times (2n+5)$: Qualsiasi rettangolo con dimensioni dispari, una dimensione un multiplo di 3 e non inferiore a $9\times5$, può essere piastrellato. Puoi partorire un rettangolo di dimensioni$6k\times(2n+5)$ che ha già dimostrato di essere piastrellabile per ridurlo a $9\times(2n+5)$. È quindi possibile partorire un rettangolo piastrellabile di dimensioni$9\times2n$, lasciando il piastrellabile $9\times5$.

Ora resta solo da dimostrarlo$3\times(2n+1)$non è piastrellabile. Questo è abbastanza ovvio quando lo provi. Gli unici modi in cui puoi riempire il bordo corto del rettangolo creeranno un file$3\times2$bloccare. Quindi il rettangolo inevitabilmente si riduce all'audibile$3\times1$forma.

Per ricapitolare, le coppie L-tromino sono$(m,n)$ dove $m,n\ge2$, almeno uno di $m$ o $n$ è divisibile per 3 e se sono entrambi dispari allora $m,n\ge5$.