7
$\begingroup$

Grogg colors of each of the edges of a tetrahedron either purple or orange. Two colorings are considered the same if you can rotate one to produce the other. How many distinct colorings can Grogg make?

$\endgroup$
0
12
$\begingroup$

By enumeration, there are $12$

There is one where all six edges are purple

There is one where five edges are purple and one is orange

There are two where four edges are purple and two are orange: either the orange edges are sharing a vertex or they are on opposite edges

Repeat all of these with the colours swapped over.

Finally, there are four possibilities when there are three of each colour: either one colour shares one vertex with the other colour forming a triangle, or each colour follows a single line of three edges with two different possible orientations.

With thanks to @Donald Splutterwit and @PM for their observations.

$\endgroup$
1
  • 1
    $\begingroup$ @Donald Splutterwit...Yes I think you are right. And note PM's comment. $\endgroup$ – David Quinn Feb 17 '18 at 19:12
10
$\begingroup$

The number of edge colourings of a tetrahedron with two colours is $\color{red}{12}$.

enter image description here

Edit: Note that the mirror image of the "central" configuration gives another one that I had initially overlooked, thanks to PM for bring this to my attention.

$\endgroup$
1
  • 2
    $\begingroup$ Can you not reflect in the vertical axis in your middle configuration to generate a further colouring? $\endgroup$ – PM. Feb 17 '18 at 18:59
8
$\begingroup$

[Some text is adapted from one of my other answers.]

Before we can answer this question, we need to understand the rotations of the tetrahedron. You can see the rotations in the video at https://vimeo.com/90519331 .

Basically,

  1. $8$ rotations are of the forms: $120^\circ$ or $240^\circ$ around an axis through one vertex and the center of the face.
  2. $3$ more rotations are $180^\circ$ around an axis through the centers of two opposite edges.
  3. $1$ more "rotation" is doing nothing (rotating by $0^\circ$).

How do we know we aren't missing any in this list of $12$ rotations? Well, there are only $4!=24$ permutations of the faces (or vertices), and half of them would turn the tetrahedron into a mirrored version of itself, which you can't do with a rotation alone.


Now, how do we get the number of colorings? There's a great theorem about counting, often called Burnside's Lemma, which says "when you want to count things with symmetry, the answer the the average (across all the operations) of the numbers of things (ignoring symmetry) that don't change when you do the operation."

So for each type of rotation, we should count how many colorings don't change:

  1. How many colorings don't change when you rotate a third of the way around a vertex? The three edges connected to the vertex must have the same color ($2$ possibilities), and the triangle of the three other edges must have the same color too ($2$ possibilities). Therefore, there are $2\times2$ colorings for each of the $8$ rotations of this type.
  2. How many colorings don't change when you rotate half way around an appropriate axis? Well, two edges end up where they started, so each of those are free to vary. And the other four edges swap in two pairs, so each of those pairs can have an arbitrary color (but two edges of the same pair must have the same color). Therefore, there are $2^4=16$ colorings for each of the $3$ rotations of this type.
  3. How many colorings don't change when you do nothing to the tetrahedron? All of them! With $2$ colors and $6$ edges, that's $2^6$.

By Burnside's Lemma, the answer is then $$\frac{8\times4+3\times16+64}{12}=\frac{144}{12}=12\text{.}$$


An aside for those who want more, Burnside's Lemma has a generalization called the Pólya enumeration theorem, which can be used to answer more specific questions like "if we had three colors, how many colorings use each color twice?", as in this midterm solution document from Professor Jacob Lurie.

$\endgroup$
4
$\begingroup$

The cycle index for the rotational symmetry group of the tetrahedron acting on the edges of the tetrahedron is $$ \frac{1}{12}(x_1^6+8x_3^2+3x_1^2x_2^2) $$ with $2$ colours yields $$ \frac{1}{12}(2^6+8(2^2)+3(2^2)(2^2))=12 $$

$\endgroup$
4
  • 2
    $\begingroup$ Do you intend to add more to this answer? I was intending to post another answer but the final calculation would be essentially the same as yours (I would just be adding context/explanation), and wanted to give you priority. $\endgroup$ – Mark S. Feb 17 '18 at 20:52
  • $\begingroup$ Thank you but please feel free to expand.. I think a complete explanation could be very long & i wasn't planning investing that much additional time on it. Thanks. $\endgroup$ – PM. Feb 17 '18 at 21:12
  • 2
    $\begingroup$ I'm aware my answer is quite concise but was a bit sad to be downvoted, especially as it was the first correct answer to be added in the presence of 2 pre-existing but incorrect answers. $\endgroup$ – PM. Feb 18 '18 at 9:32
  • 1
    $\begingroup$ You also were the first to post an answer with reasoning behind it beyond "here's the list of all of them, just trust I didn't miss any". $\endgroup$ – Mark S. Feb 18 '18 at 15:28

Not the answer you're looking for? Browse other questions tagged or ask your own question.