Constructions and Tilings · Lesson 10 of 12
When Tiling Is Impossible
“Use checkerboard colouring to prove that some even-area regions cannot be covered by dominoes.”
• Compare altered grids with the same even area. • Explain why every domino covers opposite colours. • Use unequal colour counts to prove impossibility. • Distinguish necessary conditions from guaranteed constructions. • Analyse each puzzle using the geometry of its own tile.
Removing One Square
An intact 5 × 3 rectangle has 15 squares and cannot be tiled by dominoes. Remove one square and fourteen remain. The area is now even, but does its location matter? The three source regions below let us investigate exactly that question.
In Cases A and B, a valid tiling can be shown by placing seven dominoes. In Case C, many attempts leave unwanted gaps. Repeated failure is a clue, but it is not a proof: perhaps an arrangement has simply been missed. We need a feature that every possible domino placement must preserve.
Problem
Show that Case A is tileable, rather than only stating its area is even.
- 1.Use the arrangement shown below: its first horizontal tile covers the two remaining cells of the top row.
- 2.The remaining cells can be paired legally as shown by the outlined dominoes. Each tile covers two edge-sharing neighbours.
- 3.Count seven tiles and check each of the fourteen cells belongs to one tile.
- 4.This explicit arrangement proves possibility. The same conclusion could be established by another valid arrangement.
Why an Even Area Is Not Enough
An even total tells us only that cells could be grouped numerically into pairs. A real domino has an additional geometric restriction: its cells must be neighbours along an edge. A region’s layout can prevent those required neighbour pairs from covering everything.
For intact rectangles, the row-or-column strategy guaranteed a tiling whenever the area was even. A removed square can interrupt that strategy. So a condition that was sufficient for rectangles becomes only a necessary condition for general regions. Necessary means every successful tiling must satisfy it; sufficient means satisfying it guarantees success.
We now add colours to reveal another necessary condition. The colours do not change the region or which cells are adjacent. They simply give us a way to count the two kinds of cells that every tile must pair.
Black-and-White Colouring
Colour the grid like a checkerboard, alternating the colour along each row and column. Every cell that shares an edge with a white cell is black, and every edge-neighbour of a black cell is white. Diagonal neighbours may have the same colour, but a domino cannot use them as its two cells.
A horizontal domino covers neighbouring colours in a row, so it contains one white and one black cell. A vertical domino does the same in a column. Its orientation can change, but this one-of-each property does not. Therefore k dominoes always cover k white cells and k black cells.
This colouring is equivalent to the original problem. Any legal uncoloured domino placement automatically covers opposite colours when the board is coloured. Conversely, if a coloured board is legally covered, removing the colours leaves a legal ordinary tiling. We have introduced a counting tool, not a different geometric task.
Proving Impossibility
Case C fails a condition that every domino tiling must satisfy. That lets us rule out all arrangements at once, including arrangements no one has tried. A proof of this kind explains the obstruction rather than merely recording a failed attempt.
Problem
Prove that Case C cannot be tiled.
- 1.The full 5 × 3 board has eight white cells and seven black cells when the top-left is white.
- 2.The removed top-middle cell is black. The remaining counts are eight white and six black.
- 3.Each domino covers one white and one black. Six dominoes could use all six black cells, but would cover only six of the eight white cells.
- 4.Two white cells would remain, and no domino can cover only white neighbours. Hence no domino tiling exists.
Removing another minority-colour cell from the original 5 × 3 board creates the same eight-versus-six obstruction. For example, the second-row left cell is black in this colouring. Removing a majority-colour cell instead gives seven of each colour, so this particular obstruction disappears. However, the equal counts alone should not be claimed as a proof that an arbitrary region is tileable: an actual arrangement or another sufficient argument is still needed.
Other Tiling Puzzles
The final source puzzles test whether you can apply the right reasoning to the supplied tile. A different tile may cover a different number of cells or a different colour pattern. Check its shape before reusing the domino argument.
The L-shaped region consists of a 4 × 2 left block and a 2 × 2 lower-right block, making twelve cells. The source tile is an L made of three unit squares, so a possible tiling would use four such tiles. The diagram below provides an explicit arrangement. Each coloured group is a three-cell L, not a domino.
Problem
Can the shown 8 × 8 board, with top-right and bottom-left corners removed, be tiled by dominoes?
- 1.An 8 × 8 checkerboard has 32 cells of each colour.
- 2.The top-right and bottom-left corners have the same colour because the side length is even. With our top-left-white convention, both removed cells are black.
- 3.Removing them leaves 32 white cells and 30 black cells, although the total 62 is even.
- 4.Every domino covers one of each colour, so the unequal counts prove impossibility.
Unequal colour counts prove a domino tiling impossible. Equal counts do not by themselves prove every general region possible. Also, a three-cell L tile does not cover one white and one black cell in total, so do not apply the two-cell domino count to it.
Check Your Understanding
Use these questions to check the conditions behind each method, as well as the result. For a diagram-based question, follow the labels and given information rather than judging by appearance.
Quiz
What must every checkerboard domino cover?
Why does Case C fail although it has fourteen cells?
Which fact proves a particular region is tileable?
Removing two same-colour corners from an 8 × 8 checkerboard leaves which counts?
How many three-cell L tiles are used in the twelve-cell source L region?
Practice Problems
- Find a valid seven-domino tiling for Case B and label all tile pairs.
- Prove that Case C is impossible without relying on unsuccessful placements.
- Find another black cell in the full 5 × 3 board whose removal produces an impossible domino region.
- Explain why adding checkerboard colours does not alter the legal uncoloured tilings.
- Recreate the source L-shaped region and cover it with four L triominoes.
- Explain why the shown sixty-two-cell opposite-corner board cannot be tiled by thirty-one dominoes.
- State the difference between a necessary condition and a sufficient condition using these examples.
A vertical-pair arrangement with a suitable horizontal pair can cover the region; alternatively rotate Case A’s checked tiling through 180°. It gives exactly Case B.
Key Takeaways
• Even area alone does not guarantee a general region can be tiled. • Each grid domino covers one square of each checkerboard colour. • Unequal colour counts provide a proof of impossibility. • Colouring analyses the same geometry without changing adjacency. • A valid placement demonstrates possibility; repeated failure does not prove impossibility. • Different tile shapes require their own area and placement arguments.