(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)?

For the 8 by 8 grid, n=21. Marking the x elements as letters and the y as numbers, both ascending from the top left, The following should be shaded: C1, F1, B2, E2, H2, A3, D3, G3, C4, F4, B5, E5, H5, A6, D6, G6, C7, F7, B8, E8, H8. For grids with x and y > 5, n = x[(y/3)-y'] + the sum of the first (3y') terms of F; where x is the horizontal axis, y is vertical, x' is the decimal part of x/3, y' is the decimal part of y/3, and F is a set of 3 elements (in ascending order) whose total is x. (I just named it as F). Example: x=8, so F = {2,3,3}. If x = 14, F = {4,5,5}.
Example:
x=6, y=10. So F={2,2,2}
n=(6)[(10/3)-1/3] + (2)
=6(3)+2
=18+2
=20
Try it!
As for grids whose x and y < 5, just shade the center (applying the principle of the 3 by 3 grid stated in the puzzle).
;)

Posted by Ditas on 2002-10-08 22:51:09