Deceptive Combinatorics problem

[jobsism]

Here's a very interesting question:-

Suppose you are given a cube and 6 different colours. You are asked to colour each face of the cube with a different colour. If so, how many different colorings are possible?

The thing is, this question looks easy to me at first look; the answer seems to be 6! colorings (6 colors for the 1st face, 5 for the next and so on). But the fact that this question appeared in one of the toughest Olympiad level examinations, has made me think otherwise. Can anyone tell me how to solve it?

 

[willem2]

I suppose they do not count colourings that can be produced by rotating another colouring.

There's really only one way to paint the first colour on the cube, because this face can always be rotated to the same spot.
There only two ways to place the second colour, next to the first colour, or on the opposite face.
If the second colour went to the opposite face, there's only one way to place the third colour, because all the four spots are equivalent.
If the second colour went next to the first colour, there are 4 ways of placing the third colour (although 2 of them are mirror-symmetric)
All the remaining spots on the 5 colourings with 3 colours are now non-equivalent, so there are 6 ways to fill them, so there are 30 ways of coloring the cube.

 

[Number Nine]

The reason the problem is difficult is because, generally, they will count two colourings the same if one can be obtained from the other by a rotation; you need to consider the group of symmetries of the cube. I suggest researching the orbit stabilizer theorem and Burnside's lemma in abstract algebra. They will allow you to solve the problem.

 

[jobsism]

Thank you, willem2 and Number Nine for your replies! :D

I didn't quite understand willem2's solution (my fault! I'm a tubelight when it comes to combinatorics :D), but I arrived at your answer in a different way, which I think might be equivalent to yours.

I haven't yet had a look at the orbit stabilizer theorem or Burnside's lemma, but I intend to, after this post.

So here's my go at this question:- The total number of colorings possible for the cube is 6!(without taking rotations into account). Now, for each of these colorings, a certain number of rotations are possible, which causes repetitions. So, I have to find the number of rotations for each coloring. I thought of it this way:- When a cube is placed on a table, one face is always down, facing the table. Now, I can rotate the cube in ONE direction so as to change the position of THIS face. In this way, for example, after 1 rotation, this face faces leftward, after the 2nd rotation (going in one direction), it faces the top, etc. After 4 rotations, the face again comes down, and we get the position we started with. Since there are 6 faces, with 4 rotations each, 24 rotations are possible. Thus, for each coloring, 24 rotations are there, which are considered as repetitions. Since there are 6! colorings, the number of unique colorings = 6!/24 = 30.

I hope my answer isn't difficult to understand. Is this reasoning correct (I can't help but feel other repetitions have crept into the answer!) ?

 

[Number Nine]

I'm not sure if the answer is right for the cube (I haven't calculated it), but your technique won't work in general. You need to consider the exact number of possible colouring related by each rotation.

 

[Norwegian]

Hi, I understand willem2's solution, though it can be simplified like this: Color the top in the first color, 5 possibilities for the bottom, assign one more color arbitrarily, then 6 possibilities for the rest, total 6*5=30.

I also understand jobsisms solution, but he accidently arrives at the correct number of symmetries, 24, in a wrong way (many of his rotations are the in fact the same, and he misses that some symmetries are not simple rotations). 24 can be seen the following way: Imagine the cube placed on a table, now there are 6 possible faces that can be brought to the top, and for each of those, there are 4 possible ways to rotate.

Given the number 24 of symmetries, jobsisms further argument is correct, and shows an understanding of how burnside works in this simple case: There are 720 different colorings, all of which are fixed by the identity-symmetry, none are fixed by any other symmetry, so burnside then gives 720/24=30 different colorings.

 

[jobsism]

Thank you, Norwegian! :D

I had a feeling that I had repetitions in my answer. Thanks for confirming that! :)

But I'm actually very confused about this problem; a result of Burnside's lemma as stated on Wikipedia:

"In general, the number of rotationally distinct colorings of the faces of a cube in n colors is given by

(n^6 + 3n^4 + 12n^3 + 8n^2)/24

When n=6, the answer turns out to be 2226. What do you think of this?

 

[Norwegian]

"In general, the number of rotationally distinct colorings of the faces of a cube in n colors is given by

(n^6 + 3n^4 + 12n^3 + 8n^2)/24

When n=6, the answer turns out to be 2226. What do you think of this?

They allow different faces to have the same color.

 

[jobsism]

Oh, I missed that! Thanks again, Norwegian! :D

 

[bwood01]

http://www.infoocean.info/avatar1.jpg I suppose they do not count colourings that can be produced by rotating another colouring.