Guichard-Combinatorics-Graph-Theory · Problem 1.1.7
Fundamentals
Mathematics — Probability · domino-tiling
Problem
Suppose one white and one black square are removed from an board, even. Show that the remainder can be covered by dominoes.Intuitive explanation
The key insight is that a standard checkerboard coloring reveals a hidden symmetry: an board with even has equal numbers of white and black squares, so removing one of each leaves equal counts again. Since each domino covers exactly one square of each color, you just need to verify that the remaining board is connected enough for a domino tiling to exist—and the checkerboard structure guarantees this works regardless of which squares you remove.
Intuitive explanation
The key insight is that a standard checkerboard coloring reveals a hidden symmetry: an board with even has equal numbers of white and black squares, so removing one of each leaves equal counts again. Since each domino covers exactly one square of each color, you just need to verify that the remaining board is connected enough for a domino tiling to exist—and the checkerboard structure guarantees this works regardless of which squares you remove.