A domino tiling with no fault line

Question

A tiling of a rectangle by 2 by 1 dominoes has a fault line if some straight line, running the full width or height of the rectangle along grid lines, does not cut through any domino: the tiling could be split into two pieces along that line.

Prove that every domino tiling of a 6 by 6 board has a fault line. (A 5 by 6 board, by contrast, can be tiled without one.)

Accepted Answer

Every 6 by 6 domino tiling has a fault line, because the dominoes cannot supply enough crossings. Each interior line is crossed an even number of times. Take a vertical grid line one unit from the left edge. It separates a 6 by 1 strip (6 squares) from the rest. The dominoes lying entirely inside the strip cover an even number of its squares, so the number of strip squares covered by dominoes that cross the line is even; each crossing domino covers exactly one strip square, so the number of crossing dominoes is even. The same holds for any interior line, since it always cuts off a region with…

A domino tiling with no fault line

Your answer

Discussion

Learn the concepts

Related questions