9
$\begingroup$

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

$\endgroup$

1 Answer 1

7
$\begingroup$

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$.

$\endgroup$
1
  • $\begingroup$ Yes, this is the correct answer! I used an hour or so to solve this problem, not as fast as the genie. $\endgroup$ Aug 15, 2020 at 7:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.