• 0

Trianglia

Question

Posted · Report post

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?

0

Share this post


Link to post
Share on other sites

7 answers to this question

  • 0

Posted (edited) · Report post

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
0

Share this post


Link to post
Share on other sites
  • 0

Posted (edited) · Report post

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
0

Share this post


Link to post
Share on other sites
  • 0

Posted · Report post

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.

0

Share this post


Link to post
Share on other sites
  • 0

Posted · Report post

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 :)

1

Share this post


Link to post
Share on other sites
  • 0

Posted · Report post

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

0

Share this post


Link to post
Share on other sites
  • 0

Posted · Report post

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... :)

0

Share this post


Link to post
Share on other sites
  • 0

Posted · Report post

different cultures, different mores :D

0

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!


Register a new account

Sign in

Already have an account? Sign in here.


Sign In Now

  • Recently Browsing   0 members

    No registered users viewing this page.