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…
Best Answer
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.