Jump to content
BrainDen.com - Brain Teasers
  • 0

Trianglia


BMAD
 Share

Question

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?

Link to comment
Share on other sites

7 answers to this question

Recommended Posts

  • 0

I think this logic is not correct.
Consider a simple road network as below.

The prince is at point A, and wants to reach his home at B

post-54025-0-55940100-1375964154_thumb.j

Using his logic, he stays on DE (his first intersection), turns right to EF (2nd intersection), then turns left at 3rd intersection to FC,and right again on 4th intersection towards CD.

He will then keep moving on these roads only without ever going to the roads EC and DF.

Edited by DeGe
Link to comment
Share on other sites

  • 0

I think this logic is not correct.

Consider a simple road network as below.

The prince is at point A, and wants to reach his home at B

attachicon.gifTrainglia.JPG

Using his logic, he stays on DE (his first intersection), turns right to EF (2nd intersection), then turns left at 3rd intersection to FC,and right again on 4th intersection towards CD.

He will then keep moving on these roads only without ever going to the roads EC and DF.

To reach point A after leaving the castle at B, he first has to pass through the intersection at C, making D his

second intersection. He will continue to turn right onto DF, turn left at F, turn right at E, and return home. In fact, you just demonstrated one case where the prince ends up returning back at his starting point, which supports the prince's assertion.
Edited by gavinksong
Link to comment
Share on other sites

  • 0

To reach point A after leaving the castle at B, he first has to pass through the intersection at C, making D his

second intersection. He will continue to turn right onto DF, turn left at F, turn right at E, and return home. In fact, you just demonstrated one case where the prince ends up returning back at his starting point, which supports the prince's assertion.

I assumed that the prince uses this technique to get home from anywhere on the island and not necessarily for getting to that place.

Link to comment
Share on other sites

  • 0

Instead of looking as v

0...vn-1 nodes, we'll take the "state graph" where each state is composed of a tuple [node,from,direction]

node: the node you are in (one of v0...vn-1)

from: which of the 3 edges you came from (0 1 or 2)

direction: weather your next move is to the left or right (0 or 1)

So if there were n nodes then there are 6*n possible states s0...s6n-1.

Now the proof is trivial because each state has exactly 1 outgoing edge (because the move is deterministic) and exactly 1 incoming edge because given a state you can construct the previous state from it (it's too wordy to explain but just draw some state and see if you can figure out the 3 parameters of the previous state)

So you have a graph where each node has in-degree=1 and out-degree=1, if you start at some node and go forward ofcourse you're eventually gonna end up back at the original node :)

  • Upvote 1
Link to comment
Share on other sites

  • 0

In case the above proof seems fishy to you:

Keep the same definition of the "state graph" as before, the jist of the proof lies in the fact that each state has exactly 1 preceding state, so it is impossible that you will walk into a "trap" that gets you stuck in a loop because that would mean that there's a state with more than 1 preceding states which we've shown is impossible

Link to comment
Share on other sites

  • 0

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?

I can't help but mention how strange it is that he calls his mother by her first name... :)

Link to comment
Share on other sites

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

Guest
Answer this question...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.

Loading...
 Share

  • Recently Browsing   0 members

    • No registered users viewing this page.
×
×
  • Create New...