Trianglia

[BMAD]

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?

[DeGe]

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

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 August 8, 2013 by DeGe

[gavinksong]

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

Trainglia.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 August 8, 2013 by gavinksong

[DeGe]

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.

[Anza Power]

Instead of looking as v

₀...v_n-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 v₀...v_n-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 s₀...s_6n-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

[Anza Power]

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

[kestrelknight]

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

[BMAD]

different cultures, different mores