Advanced Tiling Problem (From Combinatorics)

145 Views Asked by At

Show that a 444-by-77 chessboard can be completely tiled by 1-by-6 pieces but a 44-by-777 chessboard cannot.

I have an example and can follow this for when the chessboard is a square, say 10-by-10 but don't know how to do it for a board with uneven side lengths.

1

There are 1 best solutions below

2
On

Hint: The usual approach for proving something can be tiled is to show a tiling. In this case $6$ divides $444$, so you should be able to find one.

A common approach to proving something cannot be tiled is to find a way to color the squares so that every place you put a tile covers the same number of squares of each color. As your tiles are six squares, this suggests a coloring with six colors. Can you find a regular way to color the squares so that anywhere you put a tile covers one square of each color? Then if you color a $44 \times 777$ board that way and there are different numbers of squares colored some colors, the board cannot be covered. An example would be proving you cannot take an $8 \times 8$ chessboard, remove diagonally opposite corners, and cover the remaining area with $31$ dominoes. Using the usual coloring, you have $30$ squares of one color and $32$ of the other, while each domino covers one of each, so there will be two left over.