wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> medium >> "Boxed In" Graph Riddle
        
(Message started by: k2xl on Feb 18^th, 2008, 10:25am)

Title: "Boxed In" Graph Riddle
Post by k2xl on Feb 18^th, 2008, 10:25am

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.

Title: Re: "Boxed In" Graph Riddle
Post by towr on Feb 18^th, 2008, 11:04am

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

Title: Re: "Boxed In" Graph Riddle
Post by k2xl on Feb 18^th, 2008, 11:11am

Woops typo. Let me fix that.
*Fixed*

Title: Re: "Boxed In" Graph Riddle
Post by towr on Feb 18^th, 2008, 11:28am

Seems like a nice general pattern you can make.
[hide]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.
[/hide]

Title: Re: "Boxed In" Graph Riddle
Post by k2xl on Feb 18^th, 2008, 11:43am

Great job! You got it :-).