Drexel dragonThe Math ForumDonate to the Math Forum

Ask Dr. Math - Questions and Answers from our Archives
_____________________________________________
Associated Topics || Dr. Math Home || Search Dr. Math
_____________________________________________

Color Arrangements on the Face of a Cube

Date: 11/23/2001 at 12:51:14
From: Jhonen
Subject: Color Arrangements on the Face of a Cube

Dear Dr. Math,

I've heard the familiar problem about whether or not it is possible to 
use 3, 4, etc. colors to paint the faces of a cube such that no face 
painted one color is adjacent to another face of the same color. 
Here's another problem in the same vein which I'm not sure how to 
approach other than by trying to write out every possible combination:

Suppose you have three colors in which to paint the face of a cube, 
either red, blue, or yellow. How many different color patterns are 
there if each face of the cube must be painted red, blue, or yellow 
(assuming that two patterns are the same if the two cubes painted 
with them can be made to look the same by simply rotating one or the 
other. E.g. there is only one pattern of say, five red faces and one 
yellow).

It seems that there must be patterns of only one color, and six more 
of five of the same colors and one different one. Further, it seems as 
if there are two possibilities for the case of four sides of the same 
color and two sides of one different color, two possibilities for 
three sides of one color, and three of another. It seems that if one 
allows cubes of only two colors, that there are: 8*2*3 = 48 different 
possible color patterns.  

Is there a better way to approach this problem, and how can the 
conditions stated in the problem, which allow for each cube to have a 
color pattern of up to three colors, be dealt with?

Sincerely,
Jhonen


Date: 11/23/2001 at 18:31:48
From: Doctor Anthony
Subject: Re: Color Arrangements on the Face of a Cube

This is a problem requiring the use of Burnside's lemma. You consider 
the 24 symmetries of a cube and sum all those symmetries that keep 
colours fixed. The number of non-equivalent configurations is then the 
total sum divided by the order of the group (24 in this case).

We first find the cycle index of the group of FACE permutations 
induced by the rotational symmetries of the cube.

Looking down on the cube, label the top face 1, the bottom face 2 and 
the side faces 3, 4, 5, 6 (clockwise).

You should hold a cube and follow the way the cycle index is 
calculated as described below. The notation (1)(23)(456) = 
(x1)(x2)(x3) means that we have a permutation of 3 disjoint cycles 
in which face 1 remains fixed, face 2 moves to face 3 and 3 moves to 
face 2, face 4 moves to 5, 5 moves to 6, and 6 moves to 4. (This is 
not a possible permutation for our cube, it is just to illustrate the 
notation.) We now calculate the cycle index.

(1) e = (1)(2)(3)(4)(5)(6);  index = (x1)^6
(2) 3 permutations like (1)(2)(35)(46); index 3(x1)^2.(x2)^2
(3) 3 permutations like (1)(2)(3456); index 3(x1)^2.(x4)
(4) 3 further as above but counterclockwise; index 3(x1)^2.(x4) 
(5) 6 permutations like (15)(23)(46); index 6(x2)^3
(6) 4 permutations like (154)(236); net index 4(x3)^2
(7) 4 further as above but counterclockwise; net index 4(x3)^2

Then the cycle index is

P[x1,x2,...x6] =(1/24)[x1^6 + 3x1^2.x2^2 + 6x2^3 + 6x1^2.x4 + 8x3^2]

and the pattern inventory for these configurations is given by the 
generating function:  

(I shall use r = red, b = blue, y = yellow as the three colours.)

f(r,b,y) = (1/24)[(r+b+y)^6 + 3(r+b+y)^2.(r^2+b^2+y^2)^2 
           + 6(r^2+b^2+y^2)^3 + 6(r+b+y)^2.(r^4+b^4+y^4) 
           + 8(r^3+b^3+y^3)^2]

and putting r = 1, b = 1, y = 1 this gives

  = (1/24)[3^6 + 3(3^2)(3^2) + 6(3^3) + 6(3^2)(3) + 8(3^2)]

  = (1/24)[729 + 243 + 162 + 162 + 72]

  = 1368/24

  = 57   

So there are 57 non-equivalent configurations.

- Doctor Anthony, The Math Forum
  http://mathforum.org/dr.math/   
    

Date: 09/29/2008 at 18:40:06
From: Gopal
Subject: Distinct colored cubes

I read your article on painting the faces of a cube but I couldn't
understand how it was done.  Can we somehow use a combination formula
to do it?
 
I started with six of the same color, than five of the same color, 
then four of same color and so on.  As I moved down the chain I kept 
record of the number of distinct cubes.  So with all the same color 
there are 3 distinct cubes.  With five the same color there are 6 
distinct possibilities.  I got stuck when I had three of the same 
color painted.


Date: 09/30/2008 at 05:48:40
From: Doctor Jacques
Subject: Re: Distinct colored cubes

Hi Gopal,

The solution of this problem requires the use of a theorem of 
Burnside; that theorem is part of a discipline known as group 
theory.  I don't know if you are familiar with group theory: I will 
give you the practical method of computing the result, and some kind 
of "plausibility argument" to show you why it works (this is not a 
proof).  If you know some group theory and want the actual proof, 
please write back.

To illustrate the problem, I will start with a simpler version. We 
will consider a board of 4 squares:

  +---+---+
  | 1 | 2 |
  +---+---+
  | 3 | 4 |
  +---+---+

and try to count the number of possible ways of coloring the 4 
squares in two colors, say black and white, where two colorings are 
considered the same if they can be obtained from each other by a 
symmetry of the whole square.

If we ignore symmetries, we can color the square in 2^4 = 16 ways, 
because each of the 4 squares can be colored in two ways.  (If we had 
k colors available, there would be k^4 possible colorings).  This 
means that, if we take symmetries into account, we can only reduce 
that number.

The first step is to define precisely what are the symmetries, or 
operations, we want to consider.  Those are the permutations of the 4 
squares that correspond to a physical movement of the board 
(rotation or flipping).  Let us enumerate them.

We have the permutation that does nothing, i.e., that leaves every 
square in its place.  We will denote that operation by I (for 
Identity).  You might wonder why we bother to include it; I will come 
to that later.

Next, we have the rotations by 90 in either direction.  We will call 
those R (for Right) and L (for Left).  For example, R corresponds to 
the permutation:

  1 -> 2 -> 4 -> 3 -> 1

which is usually written as (1243).

We have the reflections across the horizontal and vertical medians, 
we will call these H and V.  We have:

  H = (13)(24)
  V = (12)(34)

We have the reflections across the diagonals, we will call these U 
and D, with:

  U = (14)(2)(3)
  D = (1)(23)(4)

(This means, for example, that D leaves 1 and 4 fixed, and 
interchanges 2 and 3)

Finally, we have the rotation by 180, which we call C:

  C = (14)(23)

In total, we have 8 operations: I, R, L, H, V, U, D, C.

This set of operations (we will call it G) has some interesting 
properties:

If A and B are two operations, then, by executing A followed by B 
(we will call that operation AB), we get another operation of the 
set.  This is a requirement for symmetries, because if neither A and 
B changes the color of any square, then the same must be true for 
AB.  For example, if we execute H followed by V, the squares move as 
follows:

  Initial position    1  2  3  4
  After H             3  4  1  2
  After HV            4  3  2  1

This means that HV sends 1 to 4, 2 to 3, 3 to 2, and 4 to 1; we can 
write this as (14)(23), which is the same as C.

Now, if, for example, we execute H twice, then each square goes back 
to its initial position, which is the operation we denoted by I (the 
one that does nothing).  This explains why we need to include I in 
our set.  Note that we would write I as (1)(2)(3)(4).

This set of operations is an example of what is called a group (in 
general, a group needs to satisfy additional requirements, but these 
are always satisfied for sets of permutations of a finite set).

After these preliminaries, we can go back to the problem of counting 
the colorings of the square.  We want to count the number of distinct 
colorings of the square, in such a way that two colorings are 
considered the same if there is some operation in G that transforms 
one into the other.  In other words, we want to partition the
2^4 = 16 colorings into sets (called orbits) in such a way that two 
colorings belong to the same orbit if there is an operation in G 
that sends one to the other.  We are interested in the number of 
orbits.

The intuitive approach is to count separately the number of distinct 
colorings invariant for each operation of G, and to take the 
average.  Burnside's theorem essentially says that this gives the 
right result; as I said before, if you know some group theory and 
want to discuss this further, please write back.

Let us start with the simplest case, namely the identity
I = (1)(2)(3)(4).  In this case, all 16 colorings are invariant under 
I (because I moves nothing), and we have 16 distinct colorings.

For the operation R = (1243), as soon as we choose a color for 
square 1, all the colors of the other squares are fixed.  Indeed, R 
sends square 1 to square 2, which must therefore have the same color 
as square 1.  In the same way, square 2 is sent to square 3, and, by 
continuing the argument, we see that all the squares must have the 
same color.  This means that there are only two possibilities, 
depending on the color we choose for square 1 : those are the 
colorings where all the squares have the same color.

For the operation H = (13)(24), we can freely choose the colors for 
squares 1 and 2, and this forces the colors of squares 3 (=1) and 4 
(=2).  This means that we have 2^2 = 4 distinct colorings invariant 
under H.

At this point, we can see a pattern emerging.  For example, H is 
written as (13)(24), i.e., as 2 cycles.  This means that the sets 
{1,3} and {2,4} are separately invariant under H: each element of 
one of these sets (cycles) is sent by H to another element of the 
same cycle.  This implies that elements of each cycle must have the 
same color; once you select a color for one element, the colors of 
the other elements of the set are fixed.  You can only choose colors 
for one element of each cycle, and the number of colorings invariant 
under the operation is 2^t, where t is the number of cycles.  Note 
that you must write down all the cycles, including those of 1 
element, like we did for I (in that case, there were 4 cycles, and 
the number of colorings was 2^4).

We should do this for all the operations in G.  However, we can 
simplify the problem a little, by noting that some operations, like 
H and V, or D and U, are "similar" in a sense that should be made 
precise.  The important point is that similar operations have the 
same number of cycles, and will therefore yield the same number of 
colorings.  We can therefore compute the number of colorings for one 
set of each class of similar operations, and multiply by the number 
of operations in the class.  This gives the following table:

  Operations  N  t  2^t  N*2^t
  I           1  4   16     16
  L,R         2  1    2      4
  H,V         2  2    4      8
  U,D         2  3    8     16
  C           1  2    4      4
  ----------------------------
  Total       8             48

In this table, N is the number of operations in each class, t is the 
number of cycles in each operation, 2^t is the number of distinct 
colorings for that operation, and N*2^t is the total number of 
colorings to take into account for the class.

As I said before, the answer to the problem is the average of all 
the distinct colorings.  As there are 8 operations, this average is 
48/8 = 6 : there are 6 distinct colorings of the square.  Using the 
order [1,2,3,4], these colorings are:

  BBBB, WWWW, BBWW, BWWB, BWWW, WBBB

In this case, it would have been easy to obtain those colorings by 
inspection.

If we had k colors instead of 2, we could repeat the same argument. 
However, in this case, there would be k possible choices for each 
square, and we would have to replace 2^t by k^t in the above table. 
This would give the number of colorings as:

  (k^4 + 2k^3 + 3k^2 + 2k)/8

This shows, for example, that, with 3 colors, there are 21 distinct 
colorings (this would already be harder to obtain by inspection).

Now, we can use the same argument for the colorings of a cube with k 

colors.  In this case, there are 24 operations, which are listed, 
with their cycle structure, in the article you refer to.

We can make a similar table.  In this case, the second column will 
contain an example of cycle structure for each class.

  Class  Structure               N  t  N*k^t
  1      (1)(2)(3)(4)(5)(6)      1  6  k^6
  2      (1)(2)(35)(46)          3  4  3k^4
  3      (1)(2)(3456)            3  3  3k^3
  4      (1)(2)(3654)            3  3  3k^3
  5      (15)(23)(46)            6  3  6k^3
  6      (154)(236)              4  2  4k^2
  7      (145)(263)              4  2  4k^2
  -----------------------------------------
  Total                         24     k^6+3k^4+12k^3+8k^2

The operations are as follows:

* Class 1 only contains the identity.

* Class 2 contains the rotations of 180 through an axis going
  through the centers of two opposite faces.

* Classes 3 and 4 contain rotations of 90 through the same axes.

* Class 5 contains rotations of 180 through the line joining the
  midpoints of two opposite edges.

* Classes 6 and 7 contains rotations of 120 through an axis joining
  two opposite vertices.

This gives the total number of distinct colorings as:

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

In the particular case of 3 colors (k=3), we get 57 colorings.

Please feel free to write back if you require further assistance.


- Doctor Jacques,  The Math Forum
  http://mathforum.org/dr.math/ 
Associated Topics:
High School Permutations and Combinations

Search the Dr. Math Library:


Find items containing (put spaces between keywords):
 
Click only once for faster results:

[ Choose "whole words" when searching for a word like age.]

all keywords, in any order at least one, that exact phrase
parts of words whole words

Submit your own question to Dr. Math

[Privacy Policy] [Terms of Use]

_____________________________________
Math Forum Home || Math Library || Quick Reference || Math Forum Search
_____________________________________

Ask Dr. MathTM
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/