Problem of the Week 1174

Chessboard Solitaire

Start with a regular 8 × 8 chessboard and place a marker on a square. Then duplicate that marker and place the new marker somewhere else on the board. Then duplicate that 2-marker configuration and place the resulting configuration of two markers on empty squares (you can translate in any direction, but you may not rotate, and you must move the whole configuration at once). Then duplicate the resulting configuration of 4 markers and place the new set on 4 open squares.

It is easy to cover the whole 8 × 8 board in this way: start with a corner square, translate rightward to fill a row, and then move up to finish.

Now start with a 7 × 7 board (49 squares). The largest number of squares that can be covered by the doubling process is 32.

Show that it is possible to cover 32 squares in this way.

Unsolved Problem (due to Raphael Robinson): The 8 × 8 result allows one to cover 64 squares on a 9 × 9, 10 × 10, or 11 × 11 board. Is it possible to cover 128 of the 144 squares on a 12 × 12 board using the doubling process starting from some single square? This is not known.

© Copyright 2014 Stan Wagon. Reproduced with permission.

[View the solution]