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)

 Subject Author Date re: One Equation prashant 2004-03-29 06:27:04 Solution Brian Smith 2003-12-02 12:03:59 Put it to Bed? brianjn 2003-06-01 16:10:52 re(3): One Equation - equation in int and mod brianjn 2003-06-01 16:01:04 re(3): Let me fix that!! brianjn 2003-05-25 20:26:17 re(2): Let me fix that!! Jackie 2003-05-19 09:46:56 re: Less than 21 Jackie 2003-05-19 09:36:04 re(2): One Equation - equation in int and mod Brian Nowell 2003-04-29 17:41:58 re: One Equation - equation in int and mod Brian Smith 2003-04-29 09:11:22 One Equation Brian Nowell 2003-04-28 16:07:01 3 x n Brian Smith 2003-04-22 06:20:52 Upper bound formula Brian Smith 2003-04-15 05:25:06 Software Solution Brian Nowell 2003-04-10 21:08:38 damn bik88 2003-03-12 14:38:37 Eureka!! - Squares Anyway Brian Nowell 2003-02-25 12:54:43 re(3): I think I got the formula. levik 2002-10-21 14:33:39 re(2): I think I got the formula. Nick Reed 2002-10-21 04:22:30 re: I think I got the formula. levik 2002-10-09 17:45:34 I think I got the formula. Ditas 2002-10-08 22:51:09 Less than 21 lucky 2002-07-23 05:59:05 re: Less than 24 Nick Reed 2002-07-22 10:58:33 re: levik 2002-07-22 10:36:22 qfqwfq qball 2002-07-22 10:35:05 No Subject qball 2002-07-22 10:32:19 Less than 24 lucky 2002-07-22 08:38:50 re: Is it? Nick Reed 2002-07-22 07:02:58 re: Hmmm... Nick Reed 2002-07-22 06:59:33 Is it? Dulanjana 2002-07-22 06:52:38 Hmmm... TomM 2002-07-22 06:28:46

 Search: Search body:
Forums (0)