(First things first - I don't know a solution to this, but the puzzle occurred to me a few hours ago, and I thought people might be interested in it)
 
Imagine a rectangular (or square) grid of any size, every square white. If the grid is "x" squares across and "y" squares high, what is the minimum number of squares ("n") that must be shaded so that no white square is adjacent to more than 2 other white squares?
(For this puzzle, diagonally adjacent squares are not considered to be adjacent)
 
So, for example, if the grid is simply a 3x3 then the only square that needs shading is the centre one, then all others squares only touch two others - i.e. for x=3 y=3, n=1
 
a) Is there an formula to calculate "n" that will work for all paired-values of "x" and "y"?
b) If not, what is "n" for a chessboard-sized x=8 y=8 (post your suggested minimum using a standard chess-like "A7" type of description for a list of all your shaded squares)?

After a little thought on this problem, I came up with a formula which gives a strong upper bound on the number of black squares.

The ideal tiling on an infinite board is a diagonal pattern.

XOOXOOXOOXOOXOO
OXOOXOOXOOXOOXO
OOXOOXOOXOOXOOX
XOOXOOXOOXOOXOO
OXOOXOOXOOXOOXO
OOXOOXOOXOOXOOX

Every white square borders exactly 2 other white squares.

This pattern can be applied to any rectangle. The number of black squares in the rectangle is ceil(x*y/3).

One black square can be removed by situating a diagonal to end in the upper left corner.

The total number of black squares in the rectangle now is ceil(x*y/3) - 1.

If a diagonal ends in the lower right corner another black square can be removed. A diagonal will end in the lower right corner if (x-y) mod 3 = 0.

The total number of black squares in the rectangle now is:
ceil(x*y/3) - 1 if (x-y) mod 3 != 0
and
ceil(x*y/3) - 2 if (x-y) mod 3 = 0
This formula works for all x,y >= 4
It gives 20 black squares for the 8x8 board.

All the white squares except half of the border squares touch exactly two other white squares. The remaining white squares touch only one other white square.

*ceil is the ceiling function. ceil rounds a non integer up to the next integer.
ceil (1.9) = 2, ceil (2) = 2, ceil (2.1) = 3
Edited on December 2, 2003, 11:53 am

Posted by Brian Smith on 2003-04-15 05:25:06