All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars
 perplexus dot info

 Grid Pathways (Posted on 2002-07-22)
(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)?

 See The Solution Submitted by Nick Reed Rating: 3.9167 (12 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
 One Equation | Comment 20 of 29 |
Nick wondered if an "x,y" equation could be formulated to describe the minimum number of shaded tiles for a given rectangle; parameters are within the descriptor.

I offered a solution for squares "Eureka!!! - Squares Anyway" and later followed up with a Software solution; useless for a calculator!!

Brian Smith has used a CEILING function (which rounds fractional parts upwards to the next integer) as against INT (which I chose, which rounds downwards).

Brian Smith's contribution is 2 formulae. These are great, but Nick sought one.

Now with many Maths situations there will be exceptions, like "if A = 0 ...".
Brian identified these but probably lowered his by one; I think that his condition should be for x,y>3 not x,y >= 3. He produced these three exceptions as:
OOOOOOOOOO, for a single row which needs no Black tiles,

OOOXOOOXO
OXOOOXOOO, for 2 rows and requires int(length/2) Black tiles,
and
OOOOOOOOO
OXXXXXXXO
OOOOOOOOO, for 3 rows requires just the length-2 Black tiles.

Brian's formulae, which are: ceil(x*y/3)-1 if (x-y) MOD 3 != 0 and ceil(x*y/3)-2 if (x-y) MOD 3 = 0, differ by a value of 1.

When (x-y) MOD 3 != 0, the value is either 1 or 2. Using the following device (x-y) will return either Zero or a One: MOD((MOD(x-y,3))^2,3); this syntax is used in MS Excel.

Applying this to ceil(x*y/3)-2 creates the formula: ceil(x*y/3)-2 + mod((mod(x-y,3))^2,3).

I have not seen the Ceiling function on any calculator so it would be great to have this formula using only the Int and mod functions. Int(x*y/3)-1 produces the same results as ceil(x*y/3)-2, except where either x or y, or both are a multiple of 3.

Anyway here is one formula that appears to do what is required for all x,y values greater than 3: n=ceil(x*y/3)-2 + mod((mod(x-y,3))^2,3).

Using Excel as a calculator and cells A1 and B1 holding the respective values of x and y,
the syntax would read as: =CEILING(A1*B1/3)-2+MOD((MOD(A1-B1,3))^2,3)
 Posted by Brian Nowell on 2003-04-28 16:07:01

 Search: Search body:
Forums (0)