The squares of a 9×9 board are colored as shown, and then its surface is covered with 40 dominoes. Each domino covers two orthogonally adjacent squares, and the uncovered square is a black square on the boundary.
A move shifts a domino along its length by one square, so that it covers one empty square and exposes another. Prove that, for each of the black squares on the board, there’s a sequence of moves that will uncover it.
This solution is by Li Zhou of Polk Community College in Winter Haven, Florida. Draw an arrow on each domino that’s covering a black square, starting on the black square and continuing through the white square. Now every black square on the board (except for the one that was exposed at the start) is covered by the tail of an arrow, and each arrow points toward a neighboring black square.
This provides an answer. For any black square that’s covered at the start, the arrows now indicate a route leading to the uncovered black square. Shifting the dominoes along this route will uncover the chosen black square.
Will every such route find its way to the uncovered square? Yes. The alternative would be some “loop” of arrows within the diagram. Any such loop would enclose an odd number of squares, and such an interior could not be tiled by dominoes. So we know it doesn’t exist.
From the 1997 Russian Olympiad for high school students, via American Mathematical Monthly, April 2004 (Problem 10960). A solution using a graph model appears in the 1999 pamphlet Mathematical Olympiads 1997-1998: Problems and Solutions From Around the World, by T. Andreescu and K. Kedlaya.
