wu :: forums - Print Page


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

        riddles >> easy >> Coloring the edges of an icosahedron
        
(Message started by: towr on Mar 24^th, 2017, 1:13am)

Title: Coloring the edges of an icosahedron
Post by towr on Mar 24^th, 2017, 1:13am

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

Title: Re: Coloring the edges of an icosahedron
Post by rloginunix on Mar 27^th, 2017, 8:11am

After an unsuccessful first attempt (https://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_general;action=display;num=1396709569;start=175#190), I've constructed an isomorphic graph on straight edges only, to make the constraints compilation easier. Much size-reduced, not for detailed study but just to get an idea (image shows work in progress):

http://www.ocf.berkeley.edu/~wwu/YaBBAttachments/icosahedron2.png

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 http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/bigtriangleup.gifLND, with opposite edges on DE and on DK, and to http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/bigtriangleup.gifLNM, 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 30-th 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 http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/bigtriangleup.gifABC 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 30-th 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.

Title: Re: Coloring the edges of an icosahedron
Post by towr on Mar 27^th, 2017, 10:54pm

What I'd really hoped for, was that I could build an object like

http://www.ocf.berkeley.edu/~wwu/YaBBAttachments/20170328_072758.jpg

without any of the elements its build from touching each other if they have the same color.

A single element looks like

http://www.ocf.berkeley.edu/~wwu/YaBBAttachments/20170328_072830.jpg

And they assemble like

http://www.ocf.berkeley.edu/~wwu/YaBBAttachments/20170328_072914.jpg

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.

Title: Re: Coloring the edges of an icosahedron
Post by dudiobugtron on Mar 28^th, 2017, 12:37am

Just some initial musings:
Any suitable 4-colouring 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 [hide]cool S-shape strategy[/hide] to get [hide]7[/hide] edges, so it's getting pretty close!

Title: Re: Coloring the edges of an icosahedron
Post by rloginunix on Mar 28^th, 2017, 8:22am

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

Title: Re: Coloring the edges of an icosahedron
Post by towr on Mar 28^th, 2017, 8:55am

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.

Title: Re: Coloring the edges of an icosahedron
Post by rloginunix on Mar 28^th, 2017, 11:35am

What prevents you from introducing the fifth color?

Title: Re: Coloring the edges of an icosahedron
Post by towr on Mar 28^th, 2017, 12:34pm

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 gift-wrapping, 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.)

Title: Re: Coloring the edges of an icosahedron
Post by Grimbal on May 2^nd, 2017, 4:26am

But the wrapping is a dead giveaway of the content, isn't it?

https://www.shapeways.com/product/47D7MP74A/five-tetrahedra-large

Title: Re: Coloring the edges of an icosahedron
Post by Grimbal on May 7^th, 2017, 6:53am

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.

Title: Re: Coloring the edges of an icosahedron
Post by Arne on Jun 13^th, 2017, 10:54am

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.

Title: Re: Coloring the edges of an icosahedron
Post by towr on Jun 13^th, 2017, 12:51pm

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.