1000.94 – Take a Walk on a Checkerboard

To get started on this problem, look at a checkerboard or draw a picture of one—8 x 8 squares, 64 squares total, alternating colors (red and black, or white and black, or whatever). Your job is to make a pathway starting from the square at the top left and ending, 64 squares later, on the square in the bottom right. Your path will go from square to square, one step at a time, no diagonal moves and no going through a square more than once. Your path will have 63 steps. Go for it.

You can report your results by saying:

  1. I did it and here is a picture of the path I drew,
  2. I haven’t got it yet but I’ll keep trying,
  3. I give up, or
  4. I think it’s impossible and here’s why.


Solution: It’s impossible! Every time you take a step you are going from a red square, say, to a black one or the other way around. If you start on a red square up in the corner, one step takes you to black. Also three steps takes you to black. In fact, any odd number of steps will take you to black. A path through every square will take you 63 steps, and this means that your path will end on a different color from the one where you started. BUT! Your path must end on the square in the lower right corner, and—did you notice?—that square is the same color as the square where you started. So it’s hopeless.