3
$\begingroup$

How many distinct ways are there to $2$-color the $8$ vertices of a cube, with colorings only considered distinct up to rotation?

$\endgroup$
  • $\begingroup$ Probably easiest to count: e.g. $0$ red, $8$ blue: one way; $1$ red, $7$ blue: one way; $2$ red, $6$ blue: three ways; etc. $\endgroup$ – Henry Jul 13 '16 at 15:32
  • $\begingroup$ This link here has many more examples of coloring polyhedra: MSE Meta. $\endgroup$ – Marko Riedel Jul 13 '16 at 20:19
7
$\begingroup$

You can use the Burnside's lemma. There are 24 rotations in the symmetry group of a cube; wikipedia page lists them all. The group acts on the set $X$ of vertex colorings, where $|X|=2^8=256$, so let's count their fixed points:

  • identity transformation: 256 (all colorings fixed)
  • 6 rotations by 90° about a 4-fold axis: these are rotations by an axis orthogonal to two faces; due to being a fixed-point, the coloring must be the same on the vertices of one of this faces. So, 2 faces, 2 colorings for each: 4 fixed points total
  • 8 rotations by 120° about a 3-fold axis:

    enter image description here

    Again, look at the orbits - there are 4 of them, so $2^4=16$ fixed points.

  • 3 rotations by 180° about a 4-fold axis: 16 fixed points each

    enter image description here

  • 6 rotations by 180° about a 2-fold axis: 16 fixed points again

Now, apply the lemma to obtain the full number of orbits (that is, the number of colorings modulo rotations):

$$|X/G| = \frac{256+6\cdot 4 + 8 \cdot 16 + 3 \cdot 16 + 6 \cdot 16}{24}=23$$

$\endgroup$
4
$\begingroup$

This looks like a job for Burnside's lemma. It says that the number of distinct ways of coloring a cube is equal to $$|X/G| = \frac{1}{|G|}\sum_{g \in G}|X^g|$$ where

  • $X$ is the full set of $2^8$ different colorings
  • $G$ is the group of valid transformations (in our case the rotations of the cube)
  • $X/G$ is the set of equivalence classes of colorings where each equivalence class contains colorings where one can be made into the other by applying an element of $G$.
  • $X^g$ is the subset of $X$ containing the colorings that look identical after applying $g$.

We divide $G$ into the following subsets (following the order of this video for reference):

  • One identity transformation: $|X^g| = 2^8$.
  • Six $90^\circ$ rotations (one clockwise and one anticlockwise for each axis) around an axis that goes through a face (axes 1, 2, 3 in the video): $|X^g| = 2^2$.
  • Three $180^\circ$ turns around the same axes: $|X^g| = 2^4$.
  • Eight $120^\circ$ turns (one clockwise and one anticlockwise for each axis) around a major diagonal (axes 4, 5, 6, 7 in the video): $|X^g| = 2^4$
  • Six $180^\circ$ rotations around an axis going through two edges (axes 8, 9, 10, 11, 12, 13): $|X^g| = 2^4$

Summing up, we get $$ |X/G| = \frac{1}{24}(2^8 + 6\cdot 2^2 + 17\cdot 2^4) = 23 $$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy