1
$\begingroup$

We are given 6 distinct colours and a cube.We have to colour each face with one of the six colours and two faces with a common edge must be coloured with different colours.How many distinct colouring ways are there?

$\endgroup$
  • 2
    $\begingroup$ Do colorings that are the same except for rotations of the entire cube count as different? $\endgroup$ – Henning Makholm Oct 28 '14 at 14:14
  • $\begingroup$ Do you consider two colorings the same if they differ by a rotation of the cube? (I'm guessing that's what you want, because you used the "permutations" tag.) Do you know Burnside's lemma? That can be useful in problems like this. $\endgroup$ – bof Oct 28 '14 at 14:22
  • $\begingroup$ yes two colourings are same if they differ by a rotation and I now that the answer is 230 $\endgroup$ – lokesh sangabattula Oct 28 '14 at 14:31
2
$\begingroup$

Just for fun, here's a solution without Burnside's lemma.

A color can be used at most twice (on two opposite faces), so the number of colors used is $3,4,5$, or $6$. We count the number of colorings for each number of colors.

$3$ colors: $\binom63=20$ ways to choose the colors, it's easy to see that all ways of applying them to the cube are rotationally indistinguishable, so $20$ ways.

$4$ colors: $\binom62\binom42=90$ ways to choose the colors (two to be used twice and two to be used once), all colorings with the chosen colors are equivalent, so $90$ ways.

$5$ colors: $\binom61\binom54=30$ ways to choose the colors. Paint two opposite faces "red" (the color chosen to be used twice) and place the cube on a table with a red side on top and bottom; the other $4$ colors are to be applied to the sides. There are $3!$ circular permutations (since the cube can be turned on its vertical axis), but we divide that by $2$ since the cube can be turned upside down, so $30\cdot3=$ 90 ways.

$6$ colors: Paint one face red. Choose a color for the opposite face ($5$ choices). Paint the other faces with the other $4$ colors (circular permutations, $3!$ choices), so $5\cdot6=$ $30$ ways.

The final snswer is $20+90+90+30=230$.

With a palette of $N$ colors, the number of indistinguishable colorings is $$\binom N3+\binom N2\binom{N-2}2+3\binom N1\binom{N-1}4+30\binom N6$$ $$=\frac1{24}\left[N(N-1)(N-2)(N^3-9N^2+32N-38)\right]$$ which agrees with Marko Riedel's solution using Burnside's lemma.

$\endgroup$
  • $\begingroup$ Very nice work and easy to follow presentation. Good to see that we arrived at the same formula for the case of $N$ colors. (+1) $\endgroup$ – Marko Riedel Oct 29 '14 at 2:50
1
$\begingroup$

Caveat: what follows could not be verified at the OEIS or elsewhere for that matter. Verification by the reader, computational e.g. by a script or otherwise is invited. Remark. No longer necessary, since a verification without Burnside has been provided.

Suppose we treat the problem of coloring a cube with at most $N$ colors where adjacent faces may not have the same color up to isomorphism under rotations. We intend to use Burnside. To do this we need to iterate over all permutations in the group of rotational automorphisms of the cube and compute the number of proper colorings that are fixed by each permutation.

There are $24$ permutations in this group. First, rotations about an axis passing through opposite vertices. No proper coloring is fixed by these rotations because the faces on the two three-cycles would have to have the same color but they are adjacent, for a contribution of zero. Second, rotations about an axis passing through the midpoints of opposite edges. These exchange the two faces incident on one of the two edges which would have to have the same color in order to be fixed under these rotations but this cannot occur in a proper coloring, again for a contribution of zero. Third, rotations about an axis passing through the midpoints of opposite faces. The 90 degree and 270 degree rotations create four-cycles of adjacent faces, which cannot be the same color in a proper coloring, again giving zero.

This leaves just two types of permutations, the identity and rotations about an axis passing through the midpoints of opposite faces by 180 degrees, which exchange opposite faces on the ring of four faces between the two faces connected by the axis. Colorings that are fixed by this rotation must have the same color on the two pairs of faces being exchanged and as these pairs are adjacent the two colors must be different. This gives $N\times (N-1)$ choices. The two faces connected by the axis can be colored independently with any one of the remaining $N-2$ colors, giving $N(N-1)(N-2)^2,$ but there are three such axes, for a total of $$3\times N(N-1)(N-2)^2.$$

The identity is the only one remaining. The number of colorings fixed by this permutation is simply the number of proper vertex colorings of the octahedron, which is given by the chromatic polynomial see e.g. MathWorld $$N(N-1)(N-2)(N^3-9N^2+29N-32).$$

It now follows by Burnside that the number of proper colorings under rotation is $$\frac{1}{24} \left(3\times N(N-1)(N-2)^2 + N(N-1)(N-2)(N^3-9N^2+29N-32)\right).$$

This gives the sequence $$0, 0, 1, 10, 55, 230, 770, 2156, 5250, 11460, 22935, 42790, 75361, \ldots$$

There are many more related links at MSE Meta on Burnside/Polya.

$\endgroup$
0
$\begingroup$

You could consider this is a direct application of http://en.wikipedia.org/wiki/Burnside%27s_lemma

What you will do is figure out your group of permutations generated by your possible rotations. $\mathscr{G} = \{e, R, RR, RRR, F, FF, FFF, FR, RF, \cdots\}$ where $R$ represents rotation to the right and $F$ represents rotation to the front (This may take a bit of time to figure out the entire group since it is not abelian; $RFRF \neq RRFF$ for example). Consider how many possibilities are left unchanged by each element of the group. Denote the colorings which are not changed by permutation $\phi$ as $X^\phi$.

$|X/\mathscr{G}| = \frac{1}{|\mathscr{G}|}\sum_{\phi\in\mathscr{G}}|X^\phi$|

Using this you can answer the even harder question of if adjacent faces are allowed to be the same color.

Notice however that in this specific case, since you have that adjacent faces must be different colors, the only time two colors can be the same are if they are opposite sides, so that makes our work much easier and we know that for all $90^\circ$ or $270^\circ$ turns there will be no possibilities that keep the coloring the same. You should check then the cases of $e, RR, FF,$ and $RRFF$(which is the same as FFRR) (and any others which I have missed, though I think those are the only four cases).

In the case of $RR$, you could have:

$~~~~~~c_4$

$c_1 ~~ c_2 ~~ c_3$

$~~~~~~c_5$

$~~~~~~c_6$

where $c_1$ must be the same as $c_3$, and $c_2$ must be the same as $c_6$.

Choose color of $c_1$ (6 choices), choose color of $c_2$ (5 remaining choices), choose color of $c_5$ (4 remaining choices), choose color of $c_4$ (4 remaining choices, the choice of $c_5$'s color does not affect $c_4$'s available choices). In doing so, we force $c_3$ to be the same as $c_1$ and we force $c_6$ to be the same as $c_2$. Thus, there are $6\cdot 5\cdot 4\cdot 4$ possible colorings which are preserved under $RR$ and $|X^{RR}| = 6\cdot 5\cdot 4\cdot 4$

Do similarly for the other cases.

$\endgroup$
0
$\begingroup$

There are only 30 distinguishable colourings. Fix one face with the first colour eg black and choose the opposite face colour in 5 ways. The remaining four faces form a ring. When you fix one colour in this ring, the other colours can be arranged in $3!$ ways.

$\endgroup$
  • $\begingroup$ That's right if you assume that all $6$ colors must be used. I don't think that's what the OP intended; if all colors had to be used, there would have been no need to say "two faces with a common edge must be coloured with different colours." $\endgroup$ – bof Oct 29 '14 at 2:53
  • $\begingroup$ who is OP here? $\endgroup$ – lokesh sangabattula Nov 2 '14 at 14:31
  • $\begingroup$ i also thought the answer was 30 but later understood that it was 230 $\endgroup$ – lokesh sangabattula Nov 11 '14 at 8:18

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.