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$ Jan 12 at 4:45
  • 1
    $\begingroup$ These are usually called L trominoes rather than dominoes. $\endgroup$
    – RobPratt
    Jan 12 at 14:16

1 Answer 1

4
$\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
    Jan 12 at 13:54
  • $\begingroup$ Yes, some tiles have 3 Bs, but that doesn’t change the fact that you need to cover all 10 As. $\endgroup$
    – RobPratt
    Jan 12 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
    Jan 12 at 14:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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