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

 Trianglia (Posted on 2002-09-11)
Trianglia is a jacked-up island where no road has a dead end, and all the crossroads are "Y" shaped.

The young prince of Trianglia mounts his horse, and is about to go on a quest to explore the land of Trianglia. He gets to the road by his palace, when the mother queen comes out and shouts:

"But Charles, how will you find your way back?".

"Don't worry Elizabeth", the prince replies, "I will turn right in every second crossroad to which I arrive, and left otherwise. Thus I shall surely return to the palace sooner or later."

Is the prince right?

 See The Solution Submitted by levik Rating: 4.0000 (5 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
 Solution | Comment 2 of 9 |
Clarifications: I'm assuming that the roads are arbitrarily crooked, but that they invariably form three-legged junctions. I'm even willing to admit non-planar graphs (maybe one road crosses over a bridge over another road).

Charles will always eventually get back to his staring place. Proof is as follows:

Model the situation with a state machine. At any instant, Charles is on a particular road, headed in a particular direction, and planning to turn either left or right at the next intersection. Thus, there are (number of roads) times 4 states. (The first times 2 is for which direction on the road, and the second times 2 is for which direction the next turn will take.)

Charles's next state is a function of nothing but his current state. Since there are a finite number of states, Charles will eventually enter some state for the second time.

However, the state transition function is fully invertable: Charles's previous state can be uniquely determined from his present state.

So we know that every state has a successor, there are a finite number of states, and no two distinct states have the same successor. The only way this can be is if each state is part of a simple loop.

 Posted by Jim Lyon on 2002-09-11 19:52:53

 Search: Search body:
Forums (0)