UVa 10733

From Algorithmist
Jump to navigation Jump to search

10733 - The Colored Cubes[edit]

Summary[edit]

All 6 sides of a cube are to be colored with paints. Each side is is painted uniformly with one color. When a selection of different colors of paint is available, how many different cubes can you make?

Two cubes are considered different if it is not possible to rotate one cube into a such position that it appears with the same coloring as the other.

Explanation[edit]

Error creating thumbnail: Unable to save thumbnail to destination
Figure 1

It's a pretty straightforward problem, if you know a bit of Polya-Burnside theory of counting.

First, you need to construct the permutation group of cube's rotations. In simple terms, it's the set of ways (permutations) in which you can relabel the cube's faces, and get an equivalent cube (under rotations.)

The cube (with the initial labelling as shown in figure 1) has 24 such ways, listed in the table below. The first column shows the final labelling of the cube, and the second one gives the corresponding permutation of faces.

Cube's arrangement Permutation Number of fixed points
abcdef(a)(b)(c)(d)(e)(f)n6
adcbfe(a)(bd)(c)(ef)n4
aecfdb(a)(bedf)(c)n3
afcebd(a)(bfde)(c)n3
badcfe(ab)(cd)(ef)n3
bcdaef(abcd)(e)(f)n3
bedfac(abe)(cdf)n2
bfdeca(abf)(cde)n2
cbadfe(ac)(b)(d)(ef)n4
cdabef(ac)(bd)(e)(f)n4
ceafbd(ac)(be)(df)n3
cfaedb(ac)(bf)(de)n3
dabcef(adcb)(e)(f)n3
dcbafe(ad)(bc)(ef)n3
debfca(adf)(bec)n2
dfbeac(ade)(bfc)n2
eafcbd(aeb)(cfd)n2
ebfdca(aecf)(b)(d)n3
ecfadb(aed)(bcf)n2
edfbac(ae)(bd)(cf)n3
faecdb(afb)(ced)n2
fbedac(afce)(b)(d)n3
fceabd(afd)(bce)n2
fdebca(af)(bd)(ce)n3


You can obtain all these permutations by first listing the most important ones - rotation aroung X, Y, and Z axes, and then listing all their possible combinations.

A fixed point of a permutation is some coloring, such that the permutation results in a cube, which has the same coloring. If each face of the cube may be assigned one of colors, and the permutation has disjoint cycles, then it has fixed points (the faces of each cycle have to be colored in the same color, there are cycles, and ways to choose colors for each.)

By Burnside's Lemma, the total number of distinct colorings is equal to the arithmetic mean of the number of fixed points of permutations. That is, the answer to the problem is given by:

If you have never heard of Polya-Burnside theory, there are still some other methods to solve this problem.

For example, you could've guessed, that the function, giving the number of colorings is a polynomial in n; obtain its values for small n by brute force, and use interpolation to find the polynomial's coefficients.

Here's another possible solution. Start by backtracking this subproblem: there are six available paints, the i-th of which must be used to color exactly sides of the cube (of course ); how many colorings are possible? Then use well-known combinations (and probably, dynamic programming) to reduce the original problem to sub-problems of this type.


For proof and details: http://en.wikipedia.org/wiki/Cycle_index#Case_study:_face_permutations_of_a_cube

http://en.wikipedia.org/wiki/P%C3%B3lya_enumeration_theorem

Input[edit]

1
2
1000
0

Output[edit]

1
10
41666792167000000