# Help with Colouring Proof for tiling a 3x9 board with L-Dominos?

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!

• 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. Jan 12 at 4:45
• These are usually called L trominoes rather than dominoes. Jan 12 at 14:16

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.

• Isn't it possible that tiles could actually have 3 Bs and 0 As. Wouldn't that be an issue in my justification?
– ENV
Jan 12 at 13:54
• Yes, some tiles have 3 Bs, but that doesn’t change the fact that you need to cover all 10 As. Jan 12 at 14:14
• 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!
– ENV
Jan 12 at 14:26