Author 
Topic: Coloring the edges of an icosahedron (Read 16919 times) 

towr
wu::riddles Moderator Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730

Is it possible, using (at most) four colors, to color the edges of an icosahedron in such a way that each edge's colors are different from those of its adjacent and opposite edges? In the attached images, red edges are adjacent to the blue one (i.e. edges on the same triangle), and green ones are opposite the blue one (i.e. opposite on a quadrilateral made of two adjacent triangles).

« Last Edit: Mar 24^{th}, 2017, 1:25am by towr » 
IP Logged 
Wikipedia, Google, Mathworld, Integer sequence DB



rloginunix
Uberpuzzler
Posts: 1026


Re: Coloring the edges of an icosahedron
« Reply #1 on: Mar 27^{th}, 2017, 8:11am » 
Quote Modify

After an unsuccessful first attempt, I've constructed an isomorphic graph on straight edges only, to make the constraints compilation easier. Much sizereduced, not for detailed study but just to get an idea (image shows work in progress): I'm taking that the solid is regular convex. Hence, each edge belongs to two (equilateral) triangles. Each triangle has two adjacent ones that carry one meaningful opposite edge each, for a total of 4 opposite edge constraints plus two sides of the same triangle constraints per triangle  another 4 constraints. For example, the edge on LN belongs to LND, with opposite edges on DE and on DK, and to LNM, with opposite edges on MF and on MH: LN  {DE, DK, MF, MH}. The meaning of each item in the set  LN can *not* be assigned any of the colors currently set for DE, DK, MF, MH. Plus the edge on LN can not have the same color with the edges on LD, ND, LM, NM. We pick 3 arbitrary (distinct) colors for any (initial) triangle and for the remaining edges we eliminate the impossible choices: if multiple colors for an edge are possible  we iterate (fork), if a possible color is unique then we set it and move on to the next edge, if no colors are possible then it's a dead end  we walk back up to the nearest fork, unsetting the colors along the way, and then repeat. That way, if we manage to assign a (legal) color to the 30th edge then we are guaranteed a solution. In my first attempt I have started with the innermost triangle and worked outward while in the second attempt I have started with ABC and worked inward, clockwise. For example, for my initial choice of color assignments the edge on AK (my starting edge) can be of only two colors: Red or Violet. However, I never managed to reach the 30th edge: my best was something like 26/27 edges. Neat idea. If it doesn't work out may be it's worth varying the solid or the constraints.


IP Logged 



towr
wu::riddles Moderator Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730


Re: Coloring the edges of an icosahedron
« Reply #2 on: Mar 27^{th}, 2017, 10:54pm » 
Quote Modify

What I'd really hoped for, was that I could build an object like without any of the elements its build from touching each other if they have the same color. A single element looks like And they assemble like The actual constraint is a bit more relaxed than I posed here. You only need to exclude two of the "opposite" edges (either lefts, or rights, depending how you look at it) Unfortunately, that doesn't seem to make it solvable either. Unless, of course, I've translated the problem incorrectly.

« Last Edit: Mar 28^{th}, 2017, 8:55am by towr » 
IP Logged 
Wikipedia, Google, Mathworld, Integer sequence DB



dudiobugtron
Uberpuzzler
Posts: 735


Re: Coloring the edges of an icosahedron
« Reply #3 on: Mar 28^{th}, 2017, 12:37am » 
Quote Modify

Just some initial musings: Any suitable 4colouring will need to have one colour on at least 8 edges, since there are 30 edges. (30/4 = 7.5) So I think a good approach to start with is to try to find 8 edges that aren't adjacent or opposite to each other; or to prove that it's impossible. I see rloginunix has a cool Sshape strategy to get 7 edges, so it's getting pretty close!

« Last Edit: Mar 28^{th}, 2017, 1:24am by dudiobugtron » 
IP Logged 



rloginunix
Uberpuzzler
Posts: 1026


Re: Coloring the edges of an icosahedron
« Reply #4 on: Mar 28^{th}, 2017, 8:22am » 
Quote Modify

I think that towr's translation is perfectly fine  most likely the origami folks are being loose with the instructions language which may be fine in an everyday sense but is not tight enough mathematically (even in some hard science textbooks we occasionally find the "this page intentionally left blank" pearls). In any case, I am afraid that I am the bearer of bad news: finished the brute force enumeration  no cigar with the original 4+4 constraints requirement (unless I made some silly mistake).


IP Logged 



towr
wu::riddles Moderator Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730


Re: Coloring the edges of an icosahedron
« Reply #5 on: Mar 28^{th}, 2017, 8:55am » 
Quote Modify

It's a shame I don't have a fifth color. Then it would be easy, and I could have equal numbers of each color.


IP Logged 
Wikipedia, Google, Mathworld, Integer sequence DB



rloginunix
Uberpuzzler
Posts: 1026


Re: Coloring the edges of an icosahedron
« Reply #6 on: Mar 28^{th}, 2017, 11:35am » 
Quote Modify

What prevents you from introducing the fifth color?


IP Logged 



towr
wu::riddles Moderator Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730


Re: Coloring the edges of an icosahedron
« Reply #7 on: Mar 28^{th}, 2017, 12:34pm » 
Quote Modify

Literally, physically not having it. I only have 4 colors of quality paper that go well together. And I haven't even been able to find more of those recently, let alone other colors. I like using constructions like this as giftwrapping, so not just any colored paper will do. (On the other hand, I've never had any complaints about elements of the same color touching, so that's really just for my own peace of mind.)

« Last Edit: Mar 28^{th}, 2017, 1:13pm by towr » 
IP Logged 
Wikipedia, Google, Mathworld, Integer sequence DB



Grimbal
wu::riddles Moderator Uberpuzzler
Gender:
Posts: 7526


Re: Coloring the edges of an icosahedron
« Reply #9 on: May 7^{th}, 2017, 6:53am » 
Quote Modify

Anyway, I wrote a program to search a solution with the relaxed rule (colors are excluded within any "Z" pattern). What came out is that you need to allow 2 exceptions to the rule to complete the star. Actually, if you look at a single color, you can color at most 7 edges without creating a conflict. So with 4 colors you can color up to 28 edges without a conflict. But you have 30 edges. It is a pitty you don't have 5 colors, you could do a perfectly symmetrical configuration. But you probably know that.

« Last Edit: May 7^{th}, 2017, 1:39pm by Grimbal » 
IP Logged 



Arne
Newbie
Welcome
Gender:
Posts: 6


Re: Coloring the edges of an icosahedron
« Reply #10 on: Jun 13^{th}, 2017, 10:54am » 
Quote Modify

I might be missing something completely obvious but here has to be a way to color it right? If you would convert the edges to nodes & notes to edges this would be covered by the four color theorem https://en.wikipedia.org/wiki/Four_color_theorem. And my gut feeling is that the conversion of nodes to edges and back again after coloring it would be "legal" creating valid graphs.


IP Logged 



towr
wu::riddles Moderator Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730


Re: Coloring the edges of an icosahedron
« Reply #11 on: Jun 13^{th}, 2017, 12:51pm » 
Quote Modify

The four color theorem doesn't apply. The problem is that this isn't like a simple map of contiguous regions/countries. But each country has enclaves that need to have the same color as the parent country. That additional constraint makes it that the four color theorem doesn't work.


IP Logged 
Wikipedia, Google, Mathworld, Integer sequence DB



