Paths on Checkerboards
The first 3 by 4 checkerboard has a path that visits every square starting at the black dot. The second 3 by 5 checkerboard has no path that visits every square starting at the black dot.
THE CHALLENGE
For these two checkerboards, identify which starting positions will begin paths that visit every square in the board and which ones do not. What is the difference?
EXPLORATION
Create some other sizes of checkerboards and try various starting positions on these. Do you see any patterns for which starting positions work on each board?
Notes
THE CHALLENGE & EXPLORATION
Trial and error can be quite successful with this puzzle and should be encouraged. With enough time and patience, your students will figure these out. The first challenge board has a complete path starting at any square. The second challenge board has complete paths that work from each of the white squares and none of the dark squares.
That’s an interesting result.
The question you want your students to ask at this point is: Why do we see this pattern of results?
Looking at the example paths in the introduction, an important observation is that the color of the squares will alternate along any path. This is because two squares that share a side will be of opposite colors. If you think of a complete path as an alternating list of all the squares of a board, this will be the key to seeing when it is impossible to have a complete path.
For example, look at the 3 by 5 grid in the introduction and in the challenge. It has 8 white squares and 7 black squares. A path that starts at a white square can alternate colors and work: WBWBWBWBWBWBWBW. However, a path that starts at a black square will be stuck: BWBWBWBWBWBWBW without any way of reaching the eighth W square.
For rectangular boards that have an even number of squares and hence the same number of white and black squares, a complete path can start anywhere. For rectangular boards that have an odd number of squares, complete paths must start in the corners or from squares that are the same color as the corners.
The Global Math Project has a lovely video in the Math Without Words section: