9

Amy is playing with different polyominoes. She suddenly thinks of a problem as follows.

Choose two positive integers $m,n$. If we can use only L-trominos to tessellate a $m\times n$ rectangle with no gaps, overlaps, or any square hanging out the rectangles, then we call the pair $(m,n)$ L-tromino pair.

She calls her brother Ben, and the genie, and try to figure out all L-tromino pairs. The genie is super smart and found all of them with a proof. Can you?


Problem by myself.


Here is a picture of L-tromino, if you want to see it:

enter image description here

Bass
  • 77,343
  • 8
  • 173
  • 360
Culver Kwan
  • 5,600
  • 1
  • 12
  • 51

1 Answers1

7

Obviously both dimensions of a tileable rectangle must be at least $2$. Also, since the area of a tromino is $3$, the area of a tileable rectangle is a multiple of $3$, and hence at least one of the dimensions is a multiple of 3.

First some easy cases:

$3k\times2n$: Two trominoes form a $3\times2$ rectangle. Therefore any $3k\times2n$ rectangle is trivially tileable.

$6k\times(2n+3)$: This rectangle splits into a $6k\times3$ and a $6k\times2n$ rectangle, both of which are instances of the trivially tileable case above.

The trickest case is this:

The above cases deals with all rectangles where one of the dimensions is even. So there now remains only those with odd dimensions.

$9\times5$: This rectangle can be tiled:
enter image description here

$(6k+9) \times (2n+5)$: Any rectangle with odd dimensions, one dimension a multiple of 3, and no smaller than $9\times5$, can be tiled. You can calve off a rectangle of size $6k\times(2n+5)$ which has already been shown to be tileable to reduce it to $9\times(2n+5)$. You can then calve off a tileable rectangle of size $9\times2n$, leaving the tileable $9\times5$.

Now it just remains to be shown that $3\times(2n+1)$ is not tileable. This is fairly obvious when you try it. The only ways that you can fill the short edge of the rectangle will create a $3\times2$ block. Therefore the rectangle unavoidably gets reduced to the untileable $3\times1$ shape.

To recap, the L-tromino pairs are $(m,n)$ where $m,n\ge2$, at least one of $m$ or $n$ is divisible by 3, and if they are both odd then $m,n\ge5$.

Jaap Scherphuis
  • 53,019
  • 7
  • 120
  • 208