Author |
Topic: HARD: Trianglia II (Read 4501 times) |
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender: 
Posts: 4863
|
 |
HARD: Trianglia II
« on: Oct 25th, 2002, 7:06pm » |
 Quote  Modify
|
When the Prince of Trianglia (an island where all intersections are Ys, and no roads lead to dead ends) returned from his voyage of discovery, he issued two edicts:
1) Because he spent a month trapped by a washed-out road, new roads are to be built so that there is more than one route to every portion of Trianglia.
2) Because dirt roads are tiresome and boring, all roads will be paved with either red, yellow, or blue bricks (each road having only one color). The color of each road should be chosen so that every intersection is the meeting of roads of all three colors.
Can the Trianglians assign a color to each of the roads to satisfy the second edict? If so, how?
A quote from the "Fun Facts about Trianglia" Tourist brochure: "Trianglians are very superstitious about having things over their heads when they are travelling. There are no overpasses or tunnels anywhere in Trianglia."
Hint: You are being asked to color the Trianglian road MAP.
|
| « Last Edit: Nov 5th, 2002, 6:24pm by Icarus » |
 IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
Pietro K.C.
Full Member
 
Gender:
Posts: 213
|
|
Re: New Puzzle: Trianglia II
« Reply #1 on: Oct 26th, 2002, 5:29pm » |
Quote Modify
|
Well, the following facts about Trianglia come to mind...
Hint #1
If you treat each intersection as a vertex, and the roads as edges, then Trianglia is a 3-regular graph.
Hint #2
Since there is more than one route to every portion of Trianglia, then, for every pair of vertices, there is a simple closed path that contains them both.
Hint #3
Since there are no tunnels or overpasses, then the graph that represents the roads and intersections of Trianglia is PLANAR.
Hint #4
The problem asks if there is a 3-coloring of the edges of a planar 3-regular graph whose every pair of vertices is in some common loop. This isn't really a hint, but it helps make things clearer.
|
| « Last Edit: Oct 26th, 2002, 5:41pm by Pietro K.C. » |
IP Logged |
"I always wondered about the meaning of life. So I looked it up in the dictionary under 'L' and there it was --- the meaning of life. It was not what I expected." (Dogbert)
|
|
|
SWF
Uberpuzzler
Posts: 879
|
 |
Re: New Puzzle: Trianglia II
« Reply #2 on: Oct 27th, 2002, 9:12am » |
Quote Modify
|
I don't think I understand this question. Seems like simply connecting two points with three roads, one of each color would do it.
|
| « Last Edit: Oct 27th, 2002, 9:13am by SWF » |
IP Logged |
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: New Puzzle: Trianglia II
« Reply #3 on: Oct 27th, 2002, 3:31pm » |
Quote Modify
|
I took your suggestion that the Trianglians replace their current extensive road system with one consisting of 3 roads and 2 intersections to the Trianglian Roads Administration, but they were most uncooperative. Even pointing out how much money they would save on maintenance did not impress them. I'm afraid they are adamant on keeping their current road system!
Mathematically, what I am asking is: Given a doubly connected finite planar 3-graph, is it always possible to assign 3 colors to the edges in such a way that every vertex has all three colors present? If so, how can you do it?
Doubly-connected means that at least 2 edges have to be cut to break the graph into two separate pieces. It is equivalent to Pietro's "common loop" condition.
|
| « Last Edit: Oct 27th, 2002, 6:56pm by Icarus » |
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
Garzahd
Junior Member
Gender:
Posts: 130
|
|
Re: New Puzzle: Trianglia II
« Reply #4 on: Oct 28th, 2002, 4:37pm » |
Quote Modify
|
Well, temporarily throwing graph theory to the wind, I'm convinced that Trianglia must be a hex-grid; that is, every city block is a hexagon. This creates some bizarre conditions at the edge of town, but otherwise makes perfect sense; color all the N/S (or E/W, depending on orientation) streets red, all the NW/SE streets yellow, and all the NE/SW streets blue.
Ask the Trianglian Road Administration if they'd like to temporary rename their island "Catan".
Recovering graph theory from the wind, it seems that one must find a maximum matching, then declare all the edges/roads of the matching to be red. Then the other roads will figure out some way to alternate Y/B colors.
That's about as far as I got from the graph-theoretical view; proving that a maximum matching is always possible is left as an exercise for the reader.
|
|
IP Logged |
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: New Puzzle: Trianglia II
« Reply #5 on: Oct 28th, 2002, 6:19pm » |
Quote Modify
|
Alas! Trianglia and Catan are bitter enemies! Something about Catan stealing away a lucrative gaming contract, and leaving for Trianglia nothing but obscure riddles.
|
|
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
Garzahd
Junior Member
Gender:
Posts: 130
|
|
Re: New Puzzle: Trianglia II
« Reply #6 on: Oct 29th, 2002, 4:10pm » |
Quote Modify
|
Isn't there some theorem that states that a graph is K-colorable as long as it doesn't contain a (K+2)-clique? If so, we clearly don't have a 5-clique, so we win.
(my graph theory is fading fast, please let me know if it's only a vertex coloring (on a K+1 clique), or only simple graphs, or what.)
|
|
IP Logged |
|
|
|
Chronos
Full Member
Gender:
Posts: 288
|
|
Re: New Puzzle: Trianglia II
« Reply #7 on: Oct 30th, 2002, 12:42pm » |
Quote Modify
|
Quote:| Well, temporarily throwing graph theory to the wind, I'm convinced that Trianglia must be a hex-grid; that is, every city block is a hexagon. |
|
Not necessarily: Trianglia might, for instance, be a dodecahedron. Well, OK, it has to be flat, but you can flatten out a dodecahedron easily enough (without requiring crossings). Or it can be a truncated icosahedron (bucky or soccer ball shape), likewise flattened, or any "Fullerene tube" (a hex-tiled cylinder with one or two semi"spherical" buckyball endcaps). Or a bunch of other arrangements which are likewise not hex-tiled.
|
|
IP Logged |
|
|
|
Garzahd
Junior Member
Gender:
Posts: 130
|
|
Re: New Puzzle: Trianglia II
« Reply #8 on: Oct 30th, 2002, 2:46pm » |
Quote Modify
|
Yeah, a hexgrid was just the first idea that came to mind; I know now that there are lots of other ways. A dodecahedron is a neat example that I hadn't thought of; but I just sketched it out and it's not hard to 3-color.
And it made for a good excuse for the Catan joke, which I'm grateful someone understood.
Right now I'm fresh out of ideas besides the ever-popular Proof By Lack Of A Counterexample, so I was hoping someone else with decent graph theory knowledge will walk by.
|
|
IP Logged |
|
|
|
James Fingas
Uberpuzzler
Gender:
Posts: 949
|
|
Re: New Puzzle: Trianglia II
« Reply #9 on: Nov 1st, 2002, 11:43am » |
Quote Modify
|
Here's a start on Trianglia II.
Notice that if you pick any two colours of road, ignoring the third, then the entire roadmap of trianglia is just a series of loops, with roads that alternate colours.
Notice that the roadmap of Trianglia can be formed using the "bubble loop" method, in which you start with a single loop of road, and then add more roads by adding a loop which connects to two stretches of road already formed (any two can be picked, as long as they are on the same block, otherwise you need overpasses or underpasses). Note that you never add roads to intersections, since all intersections are 3-way.
Now take a look at some more mysterious facts: If you draw any closed curve on the ground in Trianglia, the following facts are true:
i) it cannot cross the road exactly once.
ii) if it crosses the road zero times, try again. (this one is not so much mysterious as, well, ... what am I trying to say here ...)
iii) if it crosses the road twice, both times it crosses the same colour of road! This is a corrolory of my very first observation.
iV) if it crosses three roads, they are coloured one of each colour. This is also a corrolory of my first observation.
Now starts the fun!
Notice that when you add a road using the bubble loop method, it connects with only two existing roads. If they are the same colour, then pick one more colour arbitrarily. Now you have chosen two different colours, A and B:
1) Ignore colour C for a moment. You'll see that you are connected to one or two A,B coloured loops.
2) If you are connected to one loop, then the problem is easy. Break in two the roads you connected to, and you will see that you have broken the loop in two. Now invert the colours on one part of the loop, and colour your new road with colour C. Done!
3) If you are connected to two loops, then your two loops are connected with roads only in the colour C. If the two roads you initially connected two were of different colours, invert the colours in one of the loops so that they are of the same colour.
4) Now you are only connected to roads of a single colour, A, so pick A and C, and ignore colour B for a moment.
5) If you are now connected to a single loop, then we know what to do!
6) If you are still connected to two loops, then we have a little more work to do. We have to fundamentally recolour the roads. However, if we can prove how to do this, then we can colour the roads without bothering with steps 1 to 5. So I'll leave this as an exercise for you...
|
|
IP Logged |
Doc, I'm addicted to advice! What should I do?
|
|
|
James Fingas
Uberpuzzler
Gender:
Posts: 949
|
|
Re: New Puzzle: Trianglia II
« Reply #10 on: Nov 1st, 2002, 12:02pm » |
Quote Modify
|
okay, here's an interesting thought:
Draw a closed curve containing any section of road, and any number of intersections. Count the number of roads going in/out of the curve. Now you can forget about what's inside the curve, because the possibilities for colouring the roads in/out are unchanged by what is actually in there!
i) zero roads ... (why do I even mention the zero case?)
ii) one road ... this is outlawed!
iii) two roads ... they are the same colour. Simplest form: one road, zero intersections.
iv) three roads ... they encompass all three colours, in any order. Simplest form: three roads, one intersection.
v) four roads ... There are two possibilities here: AAAA or AABB. Simplest form: two roads, zero intersections.
vi) five roads ... There are again two possibilities: AAABC or AABAC. Simplest form: four roads, one intersection.
vii) six roads ... There are three possibilities: AAAAAA or AAAABB or AABBCC. Simplest form: three roads, zero intersections.
I have not rigorously checked to see if this is true, but I find it very interesting ... and I think it's true! But feel free to test my theory out.
UPDATE: okay, it's not completely true. The four roads could also be ABAB if two intersections are inside, and this is not consistent with the two road/zero intersection interpretation. Maybe the order is not always consistent, but the theory seems to hold true in other respects...
|
| « Last Edit: Nov 1st, 2002, 12:19pm by James Fingas » |
IP Logged |
Doc, I'm addicted to advice! What should I do?
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: New Puzzle: Trianglia II
« Reply #11 on: Nov 1st, 2002, 4:00pm » |
Quote Modify
|
(I have removed the comment I originally made here. It was concerned with something similar that I did, but does not actually apply to James' remarks.)
The only rule I know that applies in general to how roads cross a simple closed curve is that the parity of the number of crossings for all three colors must be the same. For example, ABCABC is also a possibility for 6 roads (consider the interior as a hexagon with sides colored in the same sequence).
\__/
/ \
-- --
\ __ /
/ \
Proof of the color-crossing parity rule:
Cut all the roads that cross the curve at the crossings, and throw away everything outside the curve. Also throw away any road pieces with both ends on the curve, as they will not affect the parity of the crossing counts. The remaining crossings are at one end of road pieces whose other end is an intersection. So the count of these pieces of each color has the same parity of the color-crossing count. Cut each road which is completely interior to the curve in two. Since each interior road adds two pieces to the count for its color, the total count of road pieces of a color still has the same parity as the number of crossings for that color. But every road piece now has an intersection at exactly one end, and every intersection has a road piece of each color. It follows that the count of road pieces of each color must be the same (= the number of intersections). Hence the parities of the crossing counts are also the same.
|
| « Last Edit: Nov 2nd, 2002, 12:20pm by Icarus » |
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: HARD: Trianglia II
« Reply #12 on: Nov 5th, 2002, 6:33pm » |
Quote Modify
|
Since things seem to have stalled, I'll go ahead and say that I had no luck following a path similar, but not identical, to James'. I did discover a lot of neat stuff, but always got stuck just shy of the goal.
I've added a hint to my solution in the original post. If you don't want to scroll up, here it is again:
Hint: You are being asked to color the Trianglian road MAP.
If anyone can find a different solution though, I would love to see it. Particularly because as far as I can tell, it could be possible to 3-color the edges of any doubly connected 3-graph, not just planar ones. But my solution only works in the plane (or is that the Trianglian plain?).
|
| « Last Edit: Nov 5th, 2002, 6:34pm by Icarus » |
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
TimMann
Senior Riddler
Gender:
Posts: 330
|
|
The Hunting of the Snark
« Reply #13 on: Nov 5th, 2002, 11:29pm » |
Quote Modify
|
OK, so I wimped out and looked at MathWorld for information on this problem.
The relevant page is the one on snarks. Trianglia II is equivalent to asking whether a planar snark exists. The page answers this question but doesn't give the proof. It also answers Icarus's question of whether you can 3-color the edges of every non-planar, doubly connected, 3-regular graph, which is equivalent to asking whether any non-planar snark exists. For this one it does give a proof. 
By the way, Martin Gardner fans will be pleased to know that MG coined the term "snark."
|
| « Last Edit: Nov 6th, 2002, 9:37pm by TimMann » |
IP Logged |
http://tim-mann.org/
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: HARD: Trianglia II
« Reply #14 on: Nov 6th, 2002, 9:12pm » |
Quote Modify
|
Huh! I didn't know this problem had any history! I just made it up based on a result I discovered on my own a few years ago.
Still, MathWorld mentions the result without proof, so can anyone prove that there are no planar snarks?
Here is a clear statement of my hint:
You can prove it from the 4-color map theorem.
|
| « Last Edit: Nov 6th, 2002, 9:21pm by Icarus » |
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
TimMann
Senior Riddler
Gender:
Posts: 330
|
|
Re: HARD: Trianglia II
« Reply #15 on: Nov 6th, 2002, 9:31pm » |
Quote Modify
|
I did some more wimping out last night and found the proof in one of Gardner's books (The Final Recreations), where he reprints his column about snarks, with updates to reflect the fact that the 4-color theorem had been proved since he originally wrote the column.
Since I didn't work out the proof myself, I won't post it. It's pretty but uses an idea that I don't believe I'd have thought of, even after knowing what I wanted to prove. It will be interesting if you or someone else who finds it can explain how you thought of it.
It's cool that you discovered this result on your own. The person who originally proved it (Tait) was trying to prove or disprove the 4-color theorem, naturally.
|
| « Last Edit: Nov 6th, 2002, 9:33pm by TimMann » |
IP Logged |
http://tim-mann.org/
|
|
|
James Fingas
Uberpuzzler
Gender:
Posts: 949
|
|
Re: HARD: Trianglia II
« Reply #16 on: Nov 7th, 2002, 1:37pm » |
Quote Modify
|
All right, I'm following up on your MAP suggestion.
If we colour all the "blocks" in Trianglia with four colours, 1,2,3, and 4, and then assign the roads in between them with colours, depeding on which colours the blocks are on both sides of the road:
1 & 2 -> A
3 & 4 -> A
1 & 3 -> B
2 & 4 -> B
1 & 4 -> C
2 & 3 -> C
Now, saying that there are two same-coloured roads leading into an intersection is the same as saying that there are adjacent blocks coloured the same.
From the map 4-colouring theorem, we can always colour adjacent blocks different, except in the special case where the very outside block is adjacent to itself. Therefore, we can always assign the three colours so that one of each leads into an intersection.
To explain how I thought of it, Tim ... I just figured there must be a way to go from one to the other. What can we colour in? The blocks! How can we assign a check-sum to them to ensure that differently-coloured blocks always lead to differently-coloured roads? Well, that took a little fiddling, but it's there.
|
| « Last Edit: Nov 7th, 2002, 1:40pm by James Fingas » |
IP Logged |
Doc, I'm addicted to advice! What should I do?
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: HARD: Trianglia II
« Reply #17 on: Nov 7th, 2002, 5:26pm » |
Quote Modify
|
Well Done! That was essentially how I first proved it too. One improvement I discovered later was to make the 4 colors the elements of the group Z2 x Z2, then you can get the road color simply by summing the two blocks it separates. (The additive inverse of any element of this group is itself.)
As to how I came across it, I too was playing around with proving the 4-color theorem (though not with any real hope of success). I was working at a job then that often left my hands busy, but my mind inactive. So I started thinking about the 4-color theorem to pass the time. It occured to me to try finding the colors by summing a "conservative field" on the edges. It was pretty direct to see that the field was conservative iff the sum of the edge values around each vertex was zero, which in the 3-graph case reduces to the all colors different condition of this puzzle.
I tried to prove the color condition by induction on the number of faces/vertexs/edges but could never figure out how to get a coloring for a graph all of whose faces had 5 or more sides from any smaller graph (it is sufficient to prove this for 3-graphs, which always have a face with 5 or fewer sides). So there went my claim to fame and fortune! 
|
| « Last Edit: Nov 7th, 2002, 5:27pm by Icarus » |
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
Chronos
Full Member
Gender:
Posts: 288
|
|
Re: HARD: Trianglia II
« Reply #18 on: Nov 9th, 2002, 1:34pm » |
Quote Modify
|
Quote:| (it is sufficient to prove this for 3-graphs, which always have a face with 5 or fewer sides) |
|
In fact, it's sufficient for the general four-color theorem to consider the edges to be a 3-graph (that means three edges meet at each vertex, right?). If you have more edges meeting at a vertex, then you just split the vertex into multiple 3-vertices. Any coloring which works on the resulting 3-graph will also work on the original map.
|
|
IP Logged |
|
|
|
SWF
Uberpuzzler
Posts: 879
|
|
Re: HARD: Trianglia II
« Reply #19 on: Nov 10th, 2002, 5:37pm » |
Quote Modify
|
Icarus, what about the second part of the question regarding how to carry out the coloring? Systematically cycling through every permutation of colors would work, but there must be a better way. What is the most efficient way to color the roads?
The three colors at an intersection can be in either a clockwise or counterclockwise orientation. Once the orientation of the vertices is found, the coloring of the roads follows immediately. For any face the number of clockwise intersections minus the number of counterclockwise intersections must be a multiple of three. This helps reduce the number of permuations to try. For example, in a 3-edge face all intersections have the same orientation, 4-edged has two of each, 5-edged has 4 of one orientation and 1 of the other. I guess a corresponding simplification can be made for each case when coloring the faces with the 4-color theorem. At least using solid black dots and unfilled circles to mark vertex orientations makes it easy to color a hand drawn map with a black pencil.
I see what you mean about running into problems when using induction because of 5-edge faces. The 2, 3, and 4-edge faces can be trimmed out or added to a properly colored road map without much difficulty, but adding a 5-edge face sometimes requires recoloring areas distant from the new 5-edge face. Since the map will always contain at least one face with fewer than 6 edges, figuring out how to deal with the 5-edge would be the last step.
|
|
IP Logged |
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: HARD: Trianglia II
« Reply #20 on: Nov 11th, 2002, 3:44pm » |
Quote Modify
|
I'm afraid the only way I know that guarantees a solution is by the 4-color theorem first. 4-color the "blocks" (i.e. the regions created by the roads). How this is done is given by the proof of the 4-color theorem, so you better have some powerful computer resources if you want a guaranteed coloring. Fortunately, this is seldom necessary: you can usually find a 4 coloring by inspection. Once you have the coloring, assign each color to an element of the group Z2xZ2. To find the "color" of the road, add the "colors" of the two regions it borders. Since they must have different colors, the road color is never 0, leaving 3 colors for the roads. It is also easy to show that the intersections have to have all three colors present.
I played around quite a bit with the clockwise vs counterclockwise orientation, and proved that the orientation condition was necessary and sufficient. (I.e. If you can assign to the vertexes of a planar 3-graph the numbers +/-1 so that the sum around each face is divisible by 3, then you can 3-color the edges so that +1 is a ccw orientation and -1 is a cw orientation.) I was never quite able to show that it was always possible to assign orientations in this way however (except by the 4-color theorem). If you can figure out how to prove directly it can always be done, then you can be the first to prove the 4-color theorem w/o a computer.
This is why I found it interesting. I kept coming soooo close to a solution without quite making that last little bit. It's no wonder the 4-color conjecture became famous.
Tim: How does this solution compare to the one of Tait's that you found?
|
| « Last Edit: Nov 11th, 2002, 3:49pm by Icarus » |
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
TimMann
Senior Riddler
Gender:
Posts: 330
|
|
Re: HARD: Trianglia II
« Reply #21 on: Nov 12th, 2002, 1:45am » |
Quote Modify
|
Looking at Gardner's summary of Tait's proof, there are two parts.
The first part describes how to convert a vertex with more than three incident edges into several 3-vertices, such that if the regions of the new map can be 4-colored, then the same 4-coloring works for the original map. The idea is to draw a small circle around the vertex, erase everything inside the circle, then erase one segment of the circle. This part is pretty obvious. I think someone described it in different terms earlier in this thread.
The second part is just the same as what you described, including using the group Z2xZ2.
MathWorld mentions that Tait believed he had proved the 4-color theorem -- apparently there was a third part to his 1880 paper, consisting of a flawed proof that (in the later-coined terminology) there are no planar snarks. I don't know any details of that part. Gardner was kind enough not to mention it at all.
|
| « Last Edit: Nov 12th, 2002, 1:47am by TimMann » |
IP Logged |
http://tim-mann.org/
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print