Color Arrangements on the Face of a CubeDate: 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/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994- The Math Forum at NCTM. All rights reserved.
http://mathforum.org/dr.math/