wu :: forums - Print Page


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

        riddles >> hard >> Fixing the D'Armandean Maze
        
(Message started by: Icarus on Jun 14^th, 2006, 7:05pm)

Title: Fixing the D'Armandean Maze
Post by Icarus on Jun 14^th, 2006, 7:05pm

The Puzzle Master had just set down to his evening tea when the stranger came to call. Being abreast of all things in the puzzle world, the master recognized him immediately as the Count D'Armand, whose great-grandsire had created a sensation with his "D'Armandean Maze" 100 years earlier. Feeling sure that he already knew the answer, he asked the Count to state his business.

"As you know, my great-grandsire bequeathed in his will that his challenge be issued again in this year, with the same prize of one million Francs. The truth be told, this last century has been hard on my family, and to pay the prize would bankrupt us. Yet I am bound by honor and law to follow my ancestor's request. My only hope is that no one will be able to solve the maze in the month allotted. I have come to ask you if matters may be arranged so that no solution is possible."

"Let me review the nature of the maze," said the puzzle master. "If I recall, the maze itself is nothing more than a set of paths in your gardens. The paths are laid out so that each intersection is the meeting of exactly three. Your great-grandsire placed a servant at each intersection, with a supply of red and blue stones. The challengers were allowed to start in the middle of any path they chose and to wander where they will, with the injunction that they could not take again any path already traveled, until they returned to their starting point.

"Some of the servants were instructed that if a traveler took a right turn at their intersection, they were to give a red stone to the traveler if he had none, to replace a red stone with a blue, and if the traveler had a blue stone, to take it away. If the traveler chose instead to turn left, the servant was to do the opposite: give a blue stone to the stoneless, replace blue stones with red, and take red stones away. The remaining servants were given reverse instructions: exchange no stone to blue stone to red stone for those turning right, and exchange no stone to red stone to blue stone for those turning left. These instructions were given to the servants at the start of the contest, and never changed. The challenge was to arrive back at your starting point in possession of a stone. Is this correct?"

"Indeed," replied the Count. "The challenge was solved after 11 days. We will be playing by the same rules, except this time women will be allowed to participate. My hope is that by being sufficiently clever in providing instructions to the servants, a solution will be impossible. It doesn't seem likely, though."

"Actually, it might be possible," said the master. "Are there any 'overpasses' or tunnels in your garden?"

"No, my great-grandsire never had any use for that sort of thing."

"Are there any parts of the garden that are connected to the rest by a single path?"

"Just one, an island in the middle of a small lake with a single bridge connecting it. No one took it last time, though, as it was obvious that you could not come back without retracing your steps and disqualifying yourself. The bridge is in terrible repair now, and I cannot afford to fix it. I was considering closing it for safety reasons."

"Do so. Without that bridge, I guarantee you that I can fix your contest so that no one will win it. With the bridge, I fear it would be impossible."

Why was the puzzle master sure?

Title: Re: Fixing the D'Armandean Maze
Post by Grimbal on Jun 15^th, 2006, 12:57am

I think the trick is to [hide]color the paths in 3 colors in a way that no 2 paths of the same color meet at a junction[/hide].
Now how to do that?
[hide]It is a little complicated to explain, but easy to do if you reason in term of loops. Here I mean a closed circuit that has no other path in the inside. Just start with one loop and one color, then add loops adjusting the colors accordingly. It is difficult to explain exactly how to do it and to prove that it indeed works.[/hide]

Title: Re: Fixing the D'Armandean Maze
Post by Barukh on Jun 15^th, 2006, 5:50am

Interesting... (http://planetmath.org/encyclopedia/TaitColoring.html)

Title: Re: Fixing the D'Armandean Maze
Post by SMQ on Jun 15^th, 2006, 7:23am

And I can see how a [hide]three-coloring[/hide] might be translated into instructions to the servants, but where does the bridge (or lack there of) come in?

It would seem to me that it is indeed true that if you cross the bridge you cannot then return to your starting point without disqualification (depending on the exact interpretation of "take again any path already traveled"). And if you can't cross the bridge without disqualification anyway, what does it matter if it is open or closed?

Even if it is allowed that, if you start on the bridge, returning to the bridge without a stone constitutes a win rather than a disqualification (for retracing your steps to return to the middle of the bridge); wouldn't you still be [hide]returning to the color you started from[/hide] and so not be holding a stone?

--SMQ

Title: Re: Fixing the D'Armandean Maze
Post by Grimbal on Jun 15^th, 2006, 7:58am

To me "do not take again any path already travelled" applies to each portion of a path, which means that you have to return to the starting point from the other side.
But I realize that this condition isn't even necessary! You only have to instruct the servant not to do anything if the traveller leaves the junction from the path where they came.

What it changes if you remove the bridge:
[hide] Closing the bridge also means closing the path leading to it, which effectively removes one junction. If there is no choice, there must be no servant changing stones. And obviously, removing a servant changes your state (stone-wise) if you cross that junction.
It also makes it impossible to color the paths (at least using the incremental method I hinted at) because the loop around the lake touches itself, which is an additional constraint you will have to deal with when adjusting the colors. [/hide]

Title: Re: Fixing the D'Armandean Maze
Post by SMQ on Jun 15^th, 2006, 8:49am

(going to stop hiding the simple fact that we're considering coloring the edges of the graph...)

If you remove (or add) the bridge after coloring, sure, you need to recolor, but so long as three paths (or a loop and a path) still meet at every vertex, it should still be possible. I obviously don't know the details of your method, but Barukh's reference would seem to be saying that it has been proven possible.

I like the idea of removing the retracing requirement by suitable instructions to the servants. Here's what I would propose for instructions: [hide]Define a cyclic ordering of the three states of stones, for example None --> Red --> Blue --> None. Define a similar cyclic ordering for the edge colors, for example (I'll use different colors to avoid confusion) Orange --> Green --> Yellow --> Orange. At every intersection, if the explorer is advancing in edge color the servant should advance their stone state, and vice-versa[/hide].

What's more, if we were to allow more than three states of stones -- for example allow two-blue stones, two-red stones, or a red and a blue stone, etc. -- is should be possible to extend the method to any maze! Just [hide]take any edge coloring of the maze -- we don't even require a minimal coloring -- and use as many stone states as there are edge colors. Define cyclic orderings of each, and have the servants always shift an explorer's stone state the same number of steps their chosen path shifts their edge state. That way you are guaranteed that whenever you are on an edge with the same color as your starting one, you will have the same configuration of stones you started with: none.[/hide]

[edit]Better yet, so long as servants can leave the number of stones you carry unaltered (and then ignoring the trivial solution of "never give the explorer a stone"), I think it should be possible to devise a strategy for any maze using only the given three states of stones: [hide]Given any coloring of the maze, add "virtual" edge colors until the total number of edge colors is a multiple of three; now the ordered sequence of edge colors can correspond to some integer number of complete ordered sequences of stones, and you will still return to your starting point with exactly what you started with.[/hide][/edit]

--SMQ

Title: Re: Fixing the D'Armandean Maze
Post by Grimbal on Jun 15^th, 2006, 9:28am

It seems to me that a suitable coloring with the island is simply impossible.

Note: In fact we also have to assume there is no entry to the maze, at least not through a path that joins the maze via a 3-junction.

The coloring is impossible because:
[hide] Suppose we color the maze orange-green-yellow with all colors present at each junction. Let's say the bridge is orange. Then all green paths are on the mainland. Times 2 ends, that means that there is an even number of junctions with a green path. Same for the yellow. But there is an odd number of orange path ends on the mainland, which means the junctions can not all be perfectly colored.

So, a perfect coloring of the maze is impossible with the bridge. [/hide]

But regarding the method for coloring, in fact it is not as easy as I thought. It seems you can not color it incrementally, one "loop" at a time. :-/

Title: Re: Fixing the D'Armandean Maze
Post by SMQ on Jun 15^th, 2006, 9:52am

Hmm, that's pretty hard to refute. ;)

OK, I'll agree that if you are limited to only the three given stone configurations, and if, at every junction, the servant must change the configuration of stones (with the possible exception of allowing you to leave the same way you entered w/out changing the configuration), then the island -- or any point of entry, or any path with both ends at the same junction -- poses a problem to making the maze unsolvable.

The Puzzle Master inquired about the plane nature of the maze and about the island, but not directly about looped paths, although "each intersection is the meeting of exactly three" could be interpreted to exclude that possibility... sounds like we're on the right track.

--SMQ

Title: Re: Fixing the D'Armandean Maze
Post by Barukh on Jun 15^th, 2006, 10:23am

Guys, for me you are running too fast.

I agree that the statement of the problem is in alignment with the 3-coloring of the graph. However, I don’t see how such a coloring solves the problem? :-/

Regarding bridge condition: I’ve found in another source a slightly different formulation: that the 3-coloring is possible for trivalent planar, bridge-free graphs.

The condition that there are no tunnels or overpasses seems also be important here: otherwise, the corresponding graph may not be planar.

Title: Re: Fixing the D'Armandean Maze
Post by SMQ on Jun 15^th, 2006, 11:42am

on 06/15/06 at 10:23:14, Barukh wrote:

I don’t see how such a coloring solves the problem? :-/

Well, here's the method I proposed above in somewhat more detail (and no longer hidden):

Label the three possible states of the explorer's inventory None (he/she is not holding a stone), Red (he/she is holding a red stone), and Blue (he/she is holding a blue stone). Pick one of the two cyclic orderings of these states, for example None --> Red --> Blue --> None, and call it Forward; call the other ordering Reverse.

Similarly, for the three colors of the graph, pick one of the two cyclic orderings, for example Orange --> Yellow --> Green --> Orange, and call it Forward; call the other ordering Reverse.

Finally, label an intersection Clockwise if, when the colors of the paths converging at that intersection are enumerated in a clockwise manner (as seen from above) they follow the Forward cycle; label it Counterclockwise otherwise.

Now, every servant in a Clockwise intersection should move an explorer's stone state Forward (None --> Red --> Blue --> None) if they choose to turn right, and Reverse (None --> Blue --> Red --> None) if they choose to turn left. Likewise, every servant in a Counterclockwise intersection should move an explorer's stone state Forward if they choose to turn left, and Reverse if they choose to turn right.

This ensures that, for every explorer, there is a 1 to 1 correspondence between the color of the path they are taking and their inventory. Every time they have chosen to move Forward in path color a servant have moved them Forward in stone state, and every time they have chosen to move Reverse in path color a servant has moved them Reverse in stone state.

Since they begin the maze with no stones, any time they are following a path which has been colored the same as their starting path (obviously including the starting path itself), they will not be carrying a stone, and so it is impossible to return to the starting point with a stone.

As long as the graph can be perfectly three-colored, the maze can be made unsolvable. What's more, as I showed above, if either 1) explorers are allowed to carry more than one stone, or 2) servants are allowed to let an explorer pass an intersection without altering their inventory, then it is possible to make any arbitrary maze unsolvable, based on any coloring of its graph, whether perfect or not.

--SMQ

Title: Re: Fixing the D'Armandean Maze
Post by Icarus on Jun 15^th, 2006, 4:38pm

A small suggestion - not really a hint, but something that might help you keep your thoughts in order - is to use something other than colors for your edges and stones. I should hope that the cyclic nature you have already noted would tell what it is you ought to be using! ;)

Title: Re: Fixing the D'Armandean Maze
Post by Icarus on Jun 15^th, 2006, 5:05pm

on 06/15/06 at 00:57:35, Grimbal wrote:

I think the trick is to color the paths in 3 colors in a way that no 2 paths of the same color meet at a junction.
Now how to do that?
It is a little complicated to explain, but easy to do if you reason in term of loops. Here I mean a closed circuit that has no other path in the inside. Just start with one loop and one color, then add loops adjusting the colors accordingly. It is difficult to explain exactly how to do it and to prove that it indeed works.

By Barukh's link, it is more than just difficult to explain exactly how to do it, as several generations of mathematicians can attest. Indeed, no one has yet come up with a method that does not need a computer to verify that it will always work. On the other hand, actual cases are usually fairly easy to figure out by hand.

Also - you must return to your starting point from the other end of the path. Retracing even that last bit is not allowed.

Concerning looped paths: they are excluded (except for the island) by the fact that no other part of the garden is accessible by only one path. Since the loop would take up two of the 3 spots at its intersection, it would be connected to the rest of the garden by a single path.

Last, my intent was that the servants would be given exactly the same instructions as before. The only thing that can be controlled would be which servants are "right-cyclers" and which are "left-cyclers". However, if you wish to explore alternate instructions, please feel free to do so.

Title: Re: Fixing the D'Armandean Maze
Post by SMQ on Jun 15^th, 2006, 5:55pm

on 06/15/06 at 17:05:39, Icarus wrote:

Last, my intent was that the servants would be given exactly the same instructions as before. The only thing that can be controlled would be which servants are "right-cyclers" and which are "left-cyclers".

I believe my post immediately above outlines how to develop just such an arrangement given a perfect three-coloring of the maze graph (which Barukh's reference shows to be possible under exactly the conditions in the problem statement -- planar trivalent graph with no isolated regions), does it not? I can restate it using mod-3 math if you like. ;)

--SMQ

Title: Re: Fixing the D'Armandean Maze
Post by Icarus on Jun 15^th, 2006, 7:26pm

That comment was merely to clarify what my intent in the problem was, while still allowing freedom to explore things I hadn't intended. It was not meant to indicate your solution was deficient. However, I failed somehow to note that you had in fact provided a (forward) solution in your last post before mine, so I am guilty of the fault anyway. :-[

The reverse direction (that a solution is impossible if the bridge is present) is mostly, but not entirely, covered by Grimbal's remarks. He has shown that a perfect 3-coloring of the edges is impossible, but it has not yet been shown that the situation described in the riddle requires a perfect 3-coloring.

As an added challenge, can you come up with your own proof of Tait's Theorem:

All bridgeless trivalent planar graphs can be given a perfect 3-coloring of the edges if and only if the 4-color map theorem holds.

To get halfway there: Here is how you can prove that the full 4-color map theorem is equivalent to 4-coloring the faces of bridgeless trivalent planar graphs:

Clearly the full 4-color theorem implies the bridgeless trivalent restriction. Note though that the bridgeless condition is required: a graph with a bridge has at least one face that "borders itself" across the bridge.

On the other hand, given an arbitrary map, we first convert it into a graph by putting a vertex in each region and connecting adjacent regions with an edge. Now we do the same thing again: create a new graph (the co-graph) by putting a vertex in the center of each face and connecting vertexes by crossing each edge of the old graph with an edge of the new graph.

The result is a simplified version of the original map, whose boundaries are now obviously the edges and vertices of a graph. 4-coloring the faces of the new graph is equivalent to 4-coloring the vertices of the first graph, which is equivalent to 4-coloring the regions of the original map.

We now modify this graph: each vertex with more than 3 edges we can pull apart into a set of vertexes whose external edges correspond to the originals:


\|/
-o-
/|\

becomes

\    |    /
-o-o-o-o-o-o-
  /    |    \

Note that this process causes some faces that did not previously border each other to now do so, but every pair of adjacent faces before the process are still adjacent afterwards. So if we can 4-color the faces of the resultant graph (which is bridgeless trivalent), the same coloring will work for the starting graph, and for the original map.

_____________________________

Now, can you figure out the equivalence between 4-coloring the faces of a bridgeless trivalent planar graph and perfectly 3-coloring the edges?

Title: Re: Fixing the D'Armandean Maze
Post by Grimbal on Jun 16^th, 2006, 1:37am

Now I see why you are not allowed to retrace a used path. It makes it trickier to prove that the impossibility of solving the maze implies a 3-coloring is possible.

Title: Re: Fixing the D'Armandean Maze
Post by Barukh on Jun 17^th, 2006, 12:01am

on 06/15/06 at 11:42:35, SMQ wrote:

Well, here's the method I proposed above in somewhat more detail (and no longer hidden):

Very, very nice!

on 06/15/06 at 19:26:12, Icarus wrote:

As an added challenge, can you come up with your own proof of Tait's Theorem:

All bridgeless trivalent planar graphs can be given a perfect 3-coloring of the edges if and only if the 4-color map theorem holds.

The following page (http://planetmath.org/encyclopedia/ColoringsOfPlaneGraphs.html) contains a very interesting discussion of the relevant topics, including a beautiful proof of the aforementioned theorem.

It also discusses the 2-coloring of graph vertices – very much like two types of servants in D’Armandean Maze. Formally, the coloring was defined to satisfy the following property: If two colors are +1 and -1, then the sum of colors around any face is a multiple of 3. But it seems that the argument presented by SMQ, shows that the same is true for any closed path in the graph?

By the way, 3 out of 5 platonic bodies (tetrahedron, cube and dodecahedron) are examples of trivalent planar graphs on a sphere, and as such may serve wonderfully to exploit this problem. Interestingly enough, the 2-coloring of vertices in dodecahedron is highly non-symmetric: it uses 4 vertices of one color and 16 of the other.

Icarus, thanks a lot for this wonderful problem! :D BTW, is the formulation yours?

Title: Re: Fixing the D'Armandean Maze
Post by Icarus on Jun 17^th, 2006, 7:45am

>:( The challenge was to come up with a proof on your own!

Several years ago, while working a job that kept my hands busy but left my mind free, I passed the time for a while by thinking about the 4-color theorem. I rediscovered Tait's theorem, and the 2-coloring of vertices as well. Alas, just as with Tait, this failed to lead to a means of proving the 4-color theorem. I originally started off by using Z₄ as my color-group, but after a while realized, as is mentioned in Barukh's new link, that Z₂² works much better. The main advantage is that subtraction and addition are the same operation in Z₂².

Since the beans are spilled, here is the rest of my proof of Tait's theorem (by "4-coloring" and "3-coloring", I of course mean a coloring satisfying the appropriate restictions):

The edges of a bridgeless trivalent planar graph can be 3-colored if and only if its faces can be 4-colored.

If you have 4-coloring of the faces, use the elements of Z₂² (00, 01, 10, 11) as the colors. For each edge, assign it the sum of the two faces it borders. Since the faces must have different values, their sum cannot be 00. Therefore only three "colors" are used. Now add up the values of the three edges meeting at any vertex. Since each edge is the sum of the two surrounding faces, the total sums each face-value twice, and therefore must be 00. However, the only way to sum three values taken from {01, 10, 11} and come up with 00 is 01+10+11. Hence all three "colors" are present at the vertex. The edge coloring is thus the 3-coloring desired.

Conversely, if you have a 3-coloring of the edges, again use {01, 10, 11} as the colors. While this can be described for the given graph, it is somewhat easier to talk about the co-graph, where each face is replaced by a vertex, and vice-versa, as described in my previous post. The co-graph is triangular (each face is a triangle), and loopless (no vertex has an edge leading back to itself). The coloring of the old graph induces one on the new graph for which every face is surrounded by edges of all three colors.

Lemma: the colors around any closed path on the co-graph sum to 00.

Proof: Proceed by induction twice: First look at paths with no interior. Clearly a "constant" path has sum 00, since it has no edges. Now assume that all interiorless paths of length less than n sum to 00, and consider a path of length n. Since it is interiorless, at some point it must turn around, tracing the same edge twice in a row in opposite directions. Removing the turn-around leaves a path of length n-2 whose sum is 00 by assumption. The original path adds the same edge to this twice, leaving the sum at 00. Which proves the result for interiorless paths.

Now suppose that all paths with fewer than n interior faces sum to 00, and consider a path with n interior faces. At least one of those faces must border the path itself. Redirect the path around the other side(s) of the face. The face is now exterior, so the new path has 1 less interior face and so must sum to 00. But the effect of the change on the path sum is to replace 01, 10, or 11 by 10+11, 01+11, or 01+10, respectively, or vice versa. Hence the original path also had sum 00. Which proves the lemma.

From the lemma, the rest should be obvious: Choose an arbitrary vertex V and assign it a value of 00. All other vertexes are assigned a color equal to the path sum of a path attaching them to V. Since closed paths sum to 00, it does not matter which path is used - the sums will all be the same. No two adjacent vertexes can have the same color, since their sum/difference is the color of the connecting edge, and it is not 00.
__________________________

Effectively, 3-color condition amounts to saying that it represents a "conservative color field".

Note also that we can drop the "trivalent" requirement on the graph by instead requiring that a 3-coloring of the edges of an arbitrary graph satisfy the condition that at each vertex all 3 colors have the same parity: either all three have an odd number of edges (edge ends if loops are present) of that color meeting at the vertex, or all three have an even number of edge ends at the vertex. However, this condition is clumsy to state, so in the puzzle I found it more natural to have the graph be trivalent. (Yes, the formulation is my own. I've been thinking about how I could turn the 2-colored vertex result into a puzzle for a while now, and finally came up with the stones as a means of transcribing the "must sum to 0 mod 3" condition into something that is only moderately contrived.)

Title: Re: Fixing the D'Armandean Maze
Post by Grimbal on Jun 17^th, 2006, 8:34am

Anyway, thanks for this interesting incursion in graph-coloring. I knew about the 4-coloring problem (as everybody does), but I didn't know about 3-coloring of edges and 2-coloring of vertices.

Too bad there is no equivalence with 1-coloring of something. That would have been an elegant proof of the 4-coloring theorem. :)