# Deceptive Combinatorics problem

• jobsism
In summary, the question asks how many different colorings are possible for a cube with 6 different colors on each face. While the initial answer may seem to be 6! (6 factorial) colorings, the fact that this question appears in a tough Olympiad exam suggests otherwise. Upon further analysis, it is found that there are 30 unique colorings, taking into account rotations. This is due to the fact that there are only a limited number of ways to place each color on the cube, and certain rotations result in identical colorings. This problem can be solved using the orbit stabilizer theorem and Burnside's lemma in abstract algebra. However, if we allow for different faces to have the same color, the number of possible
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?

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.

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.

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!) ?

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.

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.

Thank you, Norwegian! :D

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?

"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.

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

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

Last edited by a moderator:

## 1. What is a deceptive combinatorics problem?

A deceptive combinatorics problem is a type of mathematical problem that appears to have a simple or straightforward solution, but in reality, requires a more complex approach to solve. It often involves using counterintuitive or misleading tactics to arrive at the correct solution.

## 2. How do deceptive combinatorics problems differ from other combinatorics problems?

Deceptive combinatorics problems are unique in that they often require a more creative and non-traditional approach to solve. They may also involve thinking outside of the box and using unconventional strategies to arrive at the correct solution.

## 3. What are some common examples of deceptive combinatorics problems?

Some common examples of deceptive combinatorics problems include the Monty Hall problem, the Prisoner's Dilemma, and the Birthday Paradox. These problems may seem simple at first glance, but they can be quite challenging to solve.

## 4. How can one improve their problem-solving skills when it comes to deceptive combinatorics problems?

One way to improve problem-solving skills for deceptive combinatorics problems is to practice regularly and try to approach problems from different perspectives. It can also be helpful to study various problem-solving techniques and strategies used by experts in the field.

## 5. What are some real-world applications of deceptive combinatorics problems?

Deceptive combinatorics problems have many real-world applications, particularly in fields such as computer science, economics, and game theory. They can also help individuals develop critical thinking and decision-making skills that can be useful in various situations.

Replies
1
Views
808
Replies
2
Views
837
Replies
8
Views
992
Replies
7
Views
4K
Replies
21
Views
473
Replies
4
Views
2K
Replies
3
Views
3K
Replies
1
Views
612
Replies
6
Views
1K
Replies
7
Views
1K