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

Home > Shapes
Grid Pathways (Posted on 2002-07-22) Difficulty: 5 of 5
(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: ( You must be logged in to post comments.)
  Subject Author Date
re: One Equationprashant2004-03-29 06:27:04
SolutionSolutionBrian Smith2003-12-02 12:03:59
SolutionPut it to Bed?brianjn2003-06-01 16:10:52
re(3): One Equation - equation in int and modbrianjn2003-06-01 16:01:04
Some Thoughtsre(3): Let me fix that!!brianjn2003-05-25 20:26:17
re(2): Let me fix that!!Jackie2003-05-19 09:46:56
re: Less than 21Jackie2003-05-19 09:36:04
re(2): One Equation - equation in int and modBrian Nowell2003-04-29 17:41:58
re: One Equation - equation in int and modBrian Smith2003-04-29 09:11:22
SolutionOne EquationBrian Nowell2003-04-28 16:07:01
3 x nBrian Smith2003-04-22 06:20:52
Some ThoughtsUpper bound formulaBrian Smith2003-04-15 05:25:06
Software SolutionBrian Nowell2003-04-10 21:08:38
damnbik882003-03-12 14:38:37
Eureka!! - Squares AnywayBrian Nowell2003-02-25 12:54:43
re(3): I think I got the formula.levik2002-10-21 14:33:39
re(2): I think I got the formula.Nick Reed2002-10-21 04:22:30
Questionre: I think I got the formula.levik2002-10-09 17:45:34
SolutionI think I got the formula.Ditas2002-10-08 22:51:09
Less than 21lucky2002-07-23 05:59:05
re: Less than 24Nick Reed2002-07-22 10:58:33
Some Thoughtsre:levik2002-07-22 10:36:22
qfqwfqqball2002-07-22 10:35:05
Some ThoughtsNo Subjectqball2002-07-22 10:32:19
QuestionLess than 24lucky2002-07-22 08:38:50
re: Is it?Nick Reed2002-07-22 07:02:58
Some Thoughtsre: Hmmm...Nick Reed2002-07-22 06:59:33
Is it?Dulanjana2002-07-22 06:52:38
Some ThoughtsHmmm...TomM2002-07-22 06:28:46
Please log in:
Login:
Password:
Remember me:
Sign up! | Forgot password


Search:
Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (2)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2017 by Animus Pactum Consulting. All rights reserved. Privacy Information