Newsgroups: sci.math
From: hoey@zogwarg.etl.army.mil (Dan Hoey)
Date: 15 Jan 91 17:25:48 GMT
Subject: The Dodecahedron and the Bugs

wcw07...@uxa.cso.uiuc.edu (some random student) writes:

> There is a dodecahedran (sic) with 20 verticies (sic)....
> On each vertex is an ant....

Well, this problem showed up on rec.puzzles in November, except that
credit was given to OMNI's world's hardest IQ test, the posting wasn't
riddled with misspellings, the poster (Derek Bosch) gave his name, and
he used flies instead of ants.  (If you don't think I should mention
these discrepancies, please let me know by email.)  The problem was
also suggested for the other Platonic solids and one of the
Archimedean ones.  However, I didn't see any answers back then.

cec35...@uxa.cso.uiuc.edu (Chuck Carroll) answers the question based
on the related, but not equivalent problem:

>... color 20 of the 30 edges on a regular dodecahedron blue so that
>there are two blue edges at each vertex.  Or, color ten of the edges
>red so that exactly one red edge is at each vertex.
Chuck solved this by writing a computer program, but it can be done
fairly easily by hand, as follows.  Since there are twenty blue edges
there are forty sides of blue edges, so each face has an average of
40/12=3 1/3 blue sides.  Therefore there is at least one face with
four or five blue edges.

If you draw the graph of a dodecahedron and mark the five sides of one
face blue, the rest of the coloring may be found by the procedure:

  Repeat
    1) If a vertex is incident on two blue edges, color its third edge red, and
    2) If a vertex is incident on a red edge, color its other edges blue
  until no more can be done.

The dodecahedron will be completely colored, and the blue edges will
form three closed loops.

On the other hand if you color four sides of one face blue, and the
fifth side red, and perform the above procedure, you will end up
coloring all but nine edges.  You then get to choose the color of one
of the edges (any one of the eight with a previously colored neighbor)
and that choice determines the rest of the colors by the above
procedure.  You end up with a single closed loop that divides the
dodecahedron into a double helix. (The last choice determined whether
the helix has a right- or a left-hand thread!)

By counting the colorings congruent to the ones above, we get six of
the first kind (corresponding to the six possible choices of a pair of
antipodal faces colored blue) and thirty of the second kind
(corresponding to the fifteen possible choices of a pair of antipodal
edges at the ends of the double helix and the two possible choices of
the helix's handedness).  This confirms that Chuck's program produced
the right answers.

This method easily answers the question for the tetrahedron (three
single-loop solutions, one up to congruence) and the cube (three
double-loop solutions and six single-loop solutions, one each up to
congruence).  The octahedron is not that complicated, either, though
the coloring procedure must be modified to take account of its vertex
degree being four instead of three.  The octahedron has four
double-loop solutions (one up to congruence), four single-loop
solutions (o.u.t.c.) found by inverting the double-loop coloring(s),
and twelve single-loop double helix solutions (o.u.t.c.).

I have not found the solutions for the icosahedron, and it seems much
more difficult.  As for Archimedean solids, it's anyone's guess.

Dan Hoey
Hoey@AIC.NRL.Navy.Mil