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

(In reply to Less than 21 by lucky)

to lucky: good job, you found a working pattern. as a far the solution... after tedious work I was able to calculate some equations (I'll get to that later) but yes, the minimum shaded squares for an 8x8 grid is indeed 20.

As far as a formula... I found something that works for any SQUARE grid, meaning 1x1, 2x2... 30x30...
anyhow, the function I obtained is a piecewise function; more specifically, the relationship from x to y changes depending on the domain (x).

Here are the intervals and their corresponding functions
(x= side of square. ie: for and 8x8 grid, x=8):

INTERVAL     FUNCTION

[0,2]              3x-8
[3,6]              5x-20
[7,9]              7x-38
[10,12]           9x-62
[13,15]           11x-92

etc, etc... I could go on FOREVER! (If anyone would like a more in-depth description of how I obtained these relations, just let me know.)

anyhow, so plug in 8 into f(x)= 5(x-4):
f(8)= 5(8-4) = 20

Try these equations for ANY square grid... they work!

Posted by Jackie on 2003-05-19 09:36:04