0
$\begingroup$

I define an L-Domino as a 2x2 square with one piece removed. I want to prove that it is not possible to tile a 3x9 board with L-Dominos. My initial thought is to tile the board with 3 colours such that each L-Domino covers each colour once. But this isn't actually possible, since there are ways to tile the board so that not all colours are on each tile. Instead then, I was thinking I could say using the colouring below it must be the case that adjacent tiles must always contain the same number of each colour. Namely, 2 of each colour. But we can't use an even number of tiles since $3 \cdot 9=27$ which is the number of total tiles we need to cover. But then I'm wondering that argument would be a bit too handwavy. Is there a better colouring to use for this problem? I also used the chess colouring but got stuck with that approach too.

The colouring I'm considering would be as follows:

$ XYZXYZXYZ \\ YZXYZXYZX \\ ZXYZXYZXY$

Any hints to solve this problem would be much appreciated!

$\endgroup$
2
  • 2
    $\begingroup$ You can use brute force to show that there are only two possible ways to tile the last two columns of a $3\times (2n+1)$ rectangle. Hence, it is only possible to tile if $3\times (2n+1)$ rectangle if it is possible to tile a $3\times (2n-1)$ rectangle. Then it inductively/recursively follows that it is only possible to tile a $3\times (2n+1)$ rectangle if it is possible to tile a $3\times 1$ rectangle, which is clearly false. $\endgroup$
    – Alan Abraham
    Commented Jan 12, 2022 at 4:45
  • 1
    $\begingroup$ These are usually called L trominoes rather than dominoes. $\endgroup$
    – RobPratt
    Commented Jan 12, 2022 at 14:16

1 Answer 1

Reset to default
6
$\begingroup$

Use this two-coloring, inspired by the linear programming dual variables:

ABABABABA
BBBBBBBBB
ABABABABA

Each A requires two Bs, but there are 10 As and only 17 Bs.

Alternatively, each A requires a different tile, but there are 10 As and only 9 tiles.

$\endgroup$
3
  • $\begingroup$ Isn't it possible that tiles could actually have 3 Bs and 0 As. Wouldn't that be an issue in my justification? $\endgroup$
    – ENV
    Commented Jan 12, 2022 at 13:54
  • 1
    $\begingroup$ Yes, some tiles have 3 Bs, but that doesn’t change the fact that you need to cover all 10 As. $\endgroup$
    – RobPratt
    Commented Jan 12, 2022 at 14:14
  • $\begingroup$ Oh, I see. There are 27 tiles so you need 9 L-Dominos, but each one will cover a max of 1 A so then we run into an issue. Thanks very much! $\endgroup$
    – ENV
    Commented Jan 12, 2022 at 14:26

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .