Mathematics Problem Of the Week

Fall 2005

POW #5

A Stoned Checkerboard

Consider an n´n checkerboard that has a stone placed on each square. For one round of a game, each stone must be moved to a square that is diagonally adjacent (i.e., shares a single common vertex). At the conclusion of this process, must there be a square that contains more than one stone? If so, what is the minimum possible number of squares with multiple stones?

·	·
·	·

Example: For a 2´2 checkerboard we easily see that no multiple squares are even possible, since each diagonal pair must interchange.

·	·	·
·	·	·
·	·	·

Example: For a 3´3 checkerboard, all four corner pieces must move to the center so there must be at least one multiple square. The stones on the white spaces can move in a cycle and produce no multiples. So the minimum number of multiple squares is one.

What is the minimum number of squares with multiple stones after moves for a 4´4 checkerboard? What about 9´9?

Due Friday, September 30^th at Noon.

Solutions should be submitted to Dr. R. Lock's mailbox in the Math office or sent via e-mail to rlock@stlawu.edu.