5
$\begingroup$

a pic of a cube

In the classic counting problem where you have to give the number of possible ways to paint a cube with 6 different colors,

A well-known approach is constructive counting: fixing the first color to one of the faces, assuming the cube is fixed in some position relative to that colored face, and then going about painting the rest of the faces with the remaining 5 colors.

This goes : $1 \cdot 5 \cdot 3! = 6/6 \cdot 5 \cdot 3!$

Obviously, "fixing" is equivalent to assuming that the 6 different starting options we have in the beginning for the first color are all going to end up with the same set of 6-color arrangement, with the cardinality (the number of elements in the set) being $30$.

More specifically, if we assume each element of the set is a permutation or an arrangement of the 6 colors on the cube, each of the 6 starting options enumerate the same set.

Since in this case, the problem space is quite small and visualization of why "fixing" doesn't cause problem is obvious.

But, generally in these counting problems, when you use the constructive counting method,

  1. If we have $\{a,b,c,d,e\}$ to arrange, how can we show that progressing in the order of $abcde$ and $cdeab$ (or any different order) indeed count the same set?

  2. How can you prove that your method does not miss out anything? i.e. the set constructed by the method is actually surjective? I would also really appreciate it if you can explain what the domain of this relation

  3. How can you show that your method does not over-count? i.e. the set constructed is indeed a set and does not contain any duplicate elements by choosing different options at one level of construction.

Refer to this post I was blocked from commenting on this one and my questions are aimed at different targets.

$\endgroup$

2 Answers 2

1
$\begingroup$

Maybe it was also tacitly assumed that $1+1=2$ during the counting.

On a more serious note: Missing out cases or overcounting do indeed occur when solving such problems, and hopefully they are detected by the reading community.

Now the example at hand is so simple that nobody cares for a more formal proof. (The only fine point being that one has to distinguish mirror equivalent colorings.) In fact a "formal proof" of obvious claims tends to obscure clear issues and nourishes doubts about the statements to be proven. – "Formalizing" for an intended computer proof is another matter. But computers don't have geometric insight.

$\endgroup$
0
$\begingroup$

It would be good to define your problem mathematically, you want to paint cube in different ways. I guess that it means that non-different ways are those that you can rotate cube from one to another to have exactly same sides painted.

By rotation we may assume bringing vertex to vertex and edge to edge. So there are total of 8x3=24 positions of the cube. (for each vertex there are 3 edges around)

So number of different paintings is equal to number of all permutations divided by number of cube positions. n=6!/24=30

Just define it a bit more mathematically instead of going around and counting

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .