Problem #9

Given an a×b checkerboard with each of its squares colored black or white, a "move" consists of picking one of the squares and changing its color along with the color of each of its neighbors (squares that share an edge with it). We wish to begin with an all white board and convert it to an all black board in the minimum number of moves. For example, the figure below shows how to change the color of a 3×3 board in 5 moves (upper left square, center square, upper right square, lower right square, lower left square).

This month's problem is to try to find the minimal number of moves needed for an a×b board.

This problem is more difficult than I'd thought.

Back to the Archives

Back to the Math Department Homepage.