2
$\begingroup$

A cube is about to get fully painted using $3$ different colors. Each color is being used for $2$ faces of a cube. How many different cubes can be created this way?

I saw this in a fifth grade math contest and it does not appear to be an easy problem. It took me almost ten minutes to figure out the answer (which happens to be $6$) but I did it by imagination and visualization which is not nearly as satisfactory as a rigid proof.

Could somebody offer an interpretation in terms of advanced mathematics? Group theory (see Burnside's lemma) or maybe graph theory is what comes to mind...

$\endgroup$
  • $\begingroup$ This seems to relate to Polya's Coloring Theorem: en.wikipedia.org/wiki/P%C3%B3lya_enumeration_theorem $\endgroup$ – Vladhagen Nov 11 '13 at 19:01
  • $\begingroup$ I don´t think you need advanced mathematics to solve this one. How many ways can I choose 2 objects out of 6? That´s after applying the first color. To that I multiply the number of ways to choose 2 objects out of 4 and I am left with two uncoloured faces which I will colour with the third colour. $\endgroup$ – Adam Nov 11 '13 at 19:23
  • $\begingroup$ You are missing (some of) the point, Adam. The cube has a geometric structure. That makes certain choices different from others. $\endgroup$ – Leen Droogendijk Nov 11 '13 at 19:36
  • $\begingroup$ Except, that if you rotate the cube you get, according to my calculation, a different colouring and yet it is clear that it is the same cube. So you need to divide my answer by something - number of rotations? $\endgroup$ – Adam Nov 11 '13 at 19:37
  • $\begingroup$ Yaeh, I am starting to realize it. $\endgroup$ – Adam Nov 11 '13 at 19:38
1
$\begingroup$

This one can be done with the Polya Enumeration Theorem, which requires the cycle index $Z(G)$ of the face permutation group $G$ of the cube. We now enumerate the permutations from this group by their cycle structure.

There is the identity, which contributes $$a_1^6.$$ There are rotations about diagonals connecting opposite vertices, which contribute $$4 \times 2 \times a_3^2.$$ There are the rotations about an axis passing through the centers of opposite faces, which contribute $$3\times (2 a_1^2 a_4 + a_1^2 a_2^2).$$ Finally there are rotations about an axis passing through the midpoints of opposite edges, which contribute $$6\times a_2^3.$$ It follows that the cycle index is $$Z(G) = \frac{1}{24} a_1^6 + \frac{1}{3} a_3^2 + \frac{1}{4} a_1^2 a_4 + \frac{1}{8} a_1^2 a_2^2 + \frac{1}{4} a_2^3.$$ Substituting the three colors red, green, and blue into this cycle index we get $$Z(G)(R+G+B) = 1/24\, \left( R+G+B \right) ^{6}+1/4\, \left( R+G+B \right) ^{2} \left( {R}^{4} +{G}^{4}+{B}^{4} \right)\\ +1/8\, \left( R+G+B \right) ^{2} \left( {R}^{2}+{G}^{2 }+{B}^{2} \right) ^{2}+1/3\, \left( {R}^{3}+{G}^{3}+{B}^{3} \right) ^{2}+1/4\, \left( {R}^{2}+{G}^{2}+{B}^{2} \right) ^{3}.$$ Expanding this cycle index we obtain $${B}^{6}+{B}^{5}G+{B}^{5}R+2\,{B}^{4}{G}^{2}+2\,{B}^{4}GR+2\,{B}^{4}{R}^{2}+2\,{ B}^{3}{G}^{3}+3\,{B}^{3}{G}^{2}R+3\,{B}^{3}G{R}^{2}\\+2\,{B}^{3}{R}^{3}+2\,{B}^{2 }{G}^{4}+3\,{B}^{2}{G}^{3}R+6\,{B}^{2}{G}^{2}{R}^{2}+3\,{B}^{2}G{R}^{3}+2\,{B}^ {2}{R}^{4}\\+B{G}^{5}+2\,B{G}^{4}R+3\,B{G}^{3}{R}^{2}+3\,B{G}^{2}{R}^{3}+2\,BG{R} ^{4}+B{R}^{5}+{G}^{6}+{G}^{5}R\\+2\,{G}^{4}{R}^{2}+2\,{G}^{3}{R}^{3}+2\,{G}^{2}{R }^{4}+G{R}^{5}+{R}^{6},$$ which finally gives $$[R^2G^2B^2] Z(R+G+B) = 6.$$ This generating function includes all distributions of three or fewer colors,e.g. the coefficient of $GR^5$ is one because there is only one way to paint the cube using one color five times and a second one for the remaining face. Note that we had rotations about face pairs, edge pairs and vertex pairs, which is a standard feature in the symmetry groups of regular polyhedra. The reader is invited to compute the cycle index of the symmetry group of the faces of a tetrahedron.

Here is another interesting calculation involving a cycle index.

$\endgroup$

Your Answer

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

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