wu :: forums - Print Page


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

        riddles >> hard >> Trianglia
        
(Message started by: Nicodemus on Jul 29^th, 2002, 2:21pm)

Title: Trianglia
Post by Nicodemus on Jul 29^th, 2002, 2:21pm

No one else has posted about this problem, so I thought I would. I've been working on it and I think I have a convincing argument, if not a rigorous proof, and wanted to see what other people thought.

First, a HINT: The problem didn't mention whether there were overpasses/underpasses on the island. This would indicate it wasn't relevant to the problem (or it was forgotten, but this doesn't appear to be the case). Thus we shouldn't approach this as a planar geometry problem.

SPOILER/SOLUTION(?):

The basic traversal technique of the prince is to alternate choosing left and right roads (arcs) at every intersection (node). We can view this as a sort of binary state.

Now, let's examine the problem. Starting at an arbitrary arc in the graph (the palace being by a road), we need to ensure that we never return to that arc. Since there are no dead ends and the prince never stops, the only way to prevent him from ultimately revisiting the arc is to prove that his path of travel enters an endless loop. This loop cannot contain the original starting arc.

Thus the path of traversal must enter a closed loop. Considering this as an abstract case, we can draw a loop (a circle) and an entry path (an arrow intersecting at 12 o'clock). When we enter the circle, we have a traversal state: we turn left or right, traveling around the circle clockwise or counterclockwise.

Every time we return to the entry node in the circle, we have to ensure that the traversal state is the opposite of what we entered with. So, for example, if we're moving clockwise, we entered with a left turn and must always pass 12 o'clock by making a right turn, otherwise we'd leave our circle.

Every intersection in the circle we pass inverts the traversal state. This divides the possible behaviors of circles into two categories depending on whether there are an even or odd number of intersections in the loop. If it's an even number, we would arrive back at the entry node with the same state and we'd leave the circle. If it's an off number, we would arrive back at the entry node with the inverse of the entry state, and remain in the circle; however, the next time around, we would have inverted the traversal state again, and would thus leave the circle.

Therefore, we cannot construct a circle (containing a positive number of node) which satisfies our original criteria of entering and never leaving. (And we've made no assumptions about planar connectivity, either.) Thus the island can contain no road pattern to "trap" the prince; although he may not visit the full island, he must eventually return to the palace.

Thoughts?

Title: Re: Trianglia
Post by Alex on Jul 29^th, 2002, 4:05pm

The only thing I see missing is an explanation as to why, if he is not stuck in an endless loop, he must eventually return to his palace, since the riddle does not specifically state that the roads do not extend to an infinite space. However, since Trianglia is defined as an "island" I think it's safe to assume that the island has defined boundaries beyond which the roads to not extend.

Regardless, I think you've analyzed the problem fully and correctly.

Title: Re: Trianglia
Post by Eric Yeh on Aug 2^nd, 2002, 9:13am

Nicodemus,

You are pretty much correct; this is along the lines of what I did as well. To be rigorous, somewhere in the second sentence of your second paragraph you need to invoke finiteness of the land.

Also, you can simplify the argument a bit by considering a "loop" not as any circle for which you can get to the original again, but as a true directed loop which, if you started inside (going a certain direction), you would never leave. (By this definition, a single intersection could be a part of multiple such loops! Interesting though easy sub-problem: find with proof the maximum such loops an intersection can be contained in.) Then it is clear that you can never enter such a di(rected)-loop from the outside, because by the Y-intersection property, entering a di-loop-arc from a different point than the one preceding it in the loop will give you the wrong left-right parity.

Best,
Eric

Title: Re: Trianglia
Post by James Fingas on Aug 22^nd, 2002, 10:52am

Maybe this is a more complete statement:

1) Trianglia is finite. Furthermore, the prince has a finite number of states that he can be in (four for every road--binary direction and binary turning-memory).

2) Because of this, as the prince keeps going along, he must eventually return to a state he's already been in. Let us identify the first time this happens, and call that state A. After this point, he will simply repeat the sequence of states he originally went through after state A.

3) I propose that state A must be back at the prince's home.

4) If state A is not back at his house, then he went along a path from his house to state A before getting into the loop starting with state A. Let's call the last state on this path B.

5) Let's also examine the state that the prince was in right before he got to state A the second time, and call this state C.

6) If the prince is in state A, then we know exactly which state he was in just before state A, because we know what road the prince is on, what direction he is going (telling you what intersection he came out of), and which of the two roads in the Y he turned from (since we know which way he is about to turn).

7) Therefore, only a single state can give rise to the state A. But we have two states: B and C. These cannot be the same, because then A wouldn't be the first state that the prince revisited.

8) Therefore, there can be no state B, and it must be so that state A is at the prince's home.

Title: Re: Trianglia
Post by mattian on Jul 7^th, 2004, 9:33am

There is one way Charles might never return home. If a particular segment of road between intersections resembles a mobius strip, a system could be constructed where by he never returns. Refer to the image: If Charles sets out in the directon of the orange arrow, he would never return to the castle.

Title: Re: Trianglia
Post by Grimbal on Jul 7^th, 2004, 10:08am

Hehe... even that doesn't work.

- There is not supposed to be a dead end.
- Even on that Moebius strip, after 1 turn, he will turn back to the castle, just on the wrong side of the road. Yes, on the wrong side vertically. But it is because there is a dead end. If there were another such Moebius strip, or whatever at the other end of the road, it should work.

The only way I can see to break the rule is if there are roads being built, or destroyed.

Title: Re: Trianglia
Post by mattian on Jul 7^th, 2004, 11:05am

Grimbal,

The dead end in the image is not supposed to represent a dead end - Imagine an entire network connected to the piece in the image. It wouldn't make a difference - if the prince set out in the direction of the orange arrow, he would never get to the part of the road you interpreted as a dead end.

I will update the image to accurately depict that my drawing is just part of the network and not necessarily the whole network.

Title: Re: Trianglia
Post by mattian on Jul 7^th, 2004, 11:08am

The picture has been modified to accurately depict a portion of the network. But it's irrelevant because Grimbal is right - the prince will return to the castle after the second time round the loop. My mistake. Sorry guys.

Title: Re: Trianglia
Post by mattian on Jul 7^th, 2004, 11:13am

I have bananas in my head - Grimbal is even more right than I gave him credit for. The prince would return to the castle after the first cycle around the strip but on the bottom of the road. As opposed to a non-mobius strip segment which would send the prince twice round the loop before he returned to the castle.

Is there any way that a mobius strip can help to keep the Prince from the castle? Ideas?

Title: Re: Trianglia
Post by rmsgrey on Jul 8^th, 2004, 12:26pm

The mobius strip doesn't change James Fingas' time-reversibility argument - each of the (finite number of) states the prince can be in has a unique possible predecessor (ignoring the initial state) so, since there's a finite number of possible states, meaning that he must loop eventually, he must loop back to his initial state (since no other state can be his first repeated state).

The only ways to prevent him from returning to his initial state would be: to make the number of states infinite, or to find a state with multiple possible direct predecessors.

Title: Re: Trianglia
Post by mattian on Jul 8^th, 2004, 12:31pm

This is true - I proved that to myself shortly after posting my most recent post. It's a little sad though. I thought the mobius solution to be quite interesting looking - it's a pity it's useless.

Title: Re: Trianglia
Post by tinker on Aug 31^st, 2004, 8:00am

What is one loop was connected above one loop? The prince would be trapped inside

Title: Re: Trianglia
Post by tinker on Aug 31^st, 2004, 8:08am

Upon thinking furthur, I see no way of trapping the prince with anything.