The Art Gallery Guardian

Fill a checkerboard

This was a homework problem for CSE 548. It’s also a very common puzzle.


Given a n×nn\times n checkerboard, one can put a few checkers on it. A rule transform a checkerboard to the next. The rule states one can put a new checker if and only if at least two of it’s adjacent positions (up, down, left, right) has a checker. Apply the rule until no more checker can be added. Show that if originally the checkerboard has only n1n-1 checkers, then when the process terminates, there exist cells not filled by a checker.

Consider any n1n-1 pieces that are already placed on the board. Consider the following process:

  1. Pick any piece that was never considered, so we have a filled rectangle(square) of 1×11\times 1.
  2. Find another piece that can form a larger filled rectangle from the previous rectangle.(so Manhattan distance of at most 22 from the rectangle). This means one only regard the checkers in the rectangle and the new piece, and do the transformation until nothing more can be done. It must be form a new rectangle. If the previous rectangle is a a×ba\times b rectangle, the new rectangle is among one of the following sizes: a×ba\times b(the new piece is inside the rectangle), a×(b+1),a×(b+2),(a+1)×(b+1)a\times (b+1), a\times (b+2), (a+1)\times (b+1) or (a+2)×b(a+2)\times b. Note if the new rectangle is a c×dc\times d rectangle, c+da+b+2c+d\leq a+b+2. Let the new rectangle be the one we are considering.
  3. If there is no other piece fit the description in step 2. Go to step 1.

The process will in the end form kk rectangles, such that the sum of the perimeter is at most 4(n1)4(n-1), because each time step 22 is run, we increase the perimeter of one of the rectangle by at most 4, each time step 11 is run, we create a rectangle of perimeter 4. We can run those step at most n1n-1 times because there are only n1n-1 checkers.

If any two of the rectangles can form a larger one, then the perimeter of the new rectangle is at most the sum of the two smaller one. To show this, one can consider two cases: If they overlap, then it’s clearly true. If they do not overlap, there are only 2 distinct positions. Either their diagonal touch, or their diagonals doesn’t touch. Try both and you will see this is true. (It’s hard to draw things and post on a blog).

This shows the largest filled rectangle can be produced from n1n-1 checkers have perimeter 4(n1)4(n-1), but to fill the n×nn\times n board, one need 4n4n as a perimeter. Therefore no configuration of n1n-1 checkers can result a filled board.

Posted by Chao Xu on .
Tags: puzzle.