Author |
Topic: "Boxed In" Graph Riddle (Read 460 times) |
|
k2xl
Newbie
  
Posts: 17
|
 |
"Boxed In" Graph Riddle
« on: Feb 18th, 2008, 10:25am » |
 Quote  Modify
|
Hi everyone. This is my first post. I've been an avid reader of these forums for years.
I've come up with a few riddles in the past few years, and I'd like to post them here. If hints are needed I'll post them after.
This one is called the "Bridge Game"
You have N nodes on a 2 dimensional plane (n dots on a piece of paper). You start at one of the points (let's call it A). You must trace a path to the other points. The rules are as follows:
Point X can only visit Point Y if Point X has never visited Point Y
Point X can only visit Point Y if Point Y has never visited Point X
Point X must visit a Point if it can.
-------
Example, n = 4 (points A,B,C,D)
You start at Point A
Point A > Point B
Point B > Point C
Point C > Point D
Point D > Point A
Point A > Point C
Then you've "boxed yourself in" in 5 moves. However, it is possible to do it in less...
Point A > Point B
Point B > Point C
Point C > Point D
Point D > Point B
Now C is "boxed in" in 4 nodes!
-------
What is the minimum number of lines/edges that can be drawn before you have "boxed" yourself in, AND what is the number of possible paths that can be drawn with N nodes.
I hope I explained this well. If you have any questions I'll reply and write it clearer.
|
| « Last Edit: Feb 18th, 2008, 11:12am by k2xl » |
 IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender: 
Posts: 13730
|
|
Re: "Boxed In" Graph Riddle
« Reply #1 on: Feb 18th, 2008, 11:04am » |
Quote Modify
|
Isn't (in the last example)
Quote:Point C > Point D
Point D > Point C |
|
disallowed by
Quote:| Point X can only visit Point Y if Point Y has never visited Point X |
|
?
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
k2xl
Newbie
Posts: 17
|
|
Re: "Boxed In" Graph Riddle
« Reply #2 on: Feb 18th, 2008, 11:11am » |
Quote Modify
|
Woops typo. Let me fix that.
*Fixed*
|
| « Last Edit: Feb 18th, 2008, 11:12am by k2xl » |
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: "Boxed In" Graph Riddle
« Reply #3 on: Feb 18th, 2008, 11:28am » |
Quote Modify
|
Seems like a nice general pattern you can make.
If N is even, pick an A and B, start at A go to B, then repeatedly move along two unvisited nodes back to B, till you're done.
If N is odd, start at A, and go through two unvisited nodes back to A until you visited all nodes.
So the minimum would be 3/2N - 2 in the even case, 3/2(N-1) in the odd case.
|
| « Last Edit: Feb 18th, 2008, 11:31am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
k2xl
Newbie
Posts: 17
|
|
Re: "Boxed In" Graph Riddle
« Reply #4 on: Feb 18th, 2008, 11:43am » |
Quote Modify
|
Great job! You got it  .
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print