Infosys Interview Question
Software Engineer / DevelopersThis question is not complete .. may be you are missing some part of the question ..
If you paint the cube still you will have one cube, until and unless you cut it in some plane.
6p3 wont be since we can use same colour to paint all the sides. which not includes in the 6p3
Wouldn't it be 729? Each side has three colors that it could possibly be colored. 6 different sides results in 3^6 = 729.
This problem is solved using Polya's Enumeration Formula. The specific equation for the cube is:
1/24 * (c^6 + 3*c^4 + 12*c^3 + 8*c^2)
where c is the number of colors. For 3 the value is thus 57. When I was taking combinatorics, I found that Polya's formula was the most amazing thing I'd ever seen. The original application was for enumerating unique molecules in organic chemistry (to put it VERY briefly). The formula derivation involves identifying symmetry groups, in this case rotational symetries of the cube about various axes.
The answers above are way WAY off simply because they do not take into account the rotational symetries that result in equivalent colorings.
No doubt there will be skeptics who will not believe the low number (57) above. All I can say is, this formula is defined in, "An Introduction to Abstract Algebra," by Derek John Scott Robinson, page 95. This question is a classic application of Polya's formula.
Cheers!
Important comment on my own note. The answer is quite different if the question is phrased, "each color must be used at least once".
A variation of this modified question is, how many ways can a cube be colored using 6 colors, where each color must be used once? The answer to this question is 30.
To derive this, think of the number of ways a cube can be colored. A cube has 6 faces. Pick any face. The first face can be colored with 6 colors, the second 5, the third 4, etc. This is 6! = 6 * 5 * 4 * 3 * 2 * 1. You must then divide this by the number of "cycle groups" for a cube. The cycle groups are defined as rotations about various axes that create equivalent colorings. It is beyond what I can reproduce here, but the number of cycle groups for a cube is 24 (consider it 6 * 4 if you wish, although in actuality it is 1 + 3 + 6 + 6 + 8). So, the answer is (6 * 5 * 4 * 3 * 2 * 1) / (6 * 4) = 5 * 3 * 2 = 30.
I agree to KillERdr's answer of 3^6 w/o any restrictions...
But what happens if the question had asked about the no. of ways we can paint the faces so that the adjacent faces have dissimilar colours ??? Any Takers !!!
1. 3 colours of paint.
2. Colours of paint can be combined.
3. Cube need not be coloured based on sides (i.e., you can paint abstract items).
Based on (2) or (3), you pretty much have infinte ways of colouring any cube (assuming a reasonably sized cube and brush).
I'm pretty sure this isn't what the question was asking for, but thinking outside the cube is more fun.
It's like asking how many ways can 3 toilets be used by 6 users ? (3 colors/6 sides)
_ _ _ = 6*5*4 = 6P3 = 120.
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 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 and 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
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 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 and 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
what the hell permutations???
It's so straight forward:
you have 6 positions with 3 possible options for each. It's like 6-digit number with a base of 3.
The total number of combinations is 3*3*3*3*3*3 = 3^6, which is 729
Yes, the correct answer is indeed 57 for exactly the reason ThomasT gave. As one of the posts above said, because a cube is considered a rigid object capable of 3-dimensional motion (i.e. rotations, flips, etc.), by simply taking 3^6, one is over-counting greatly. As an example, by thinking the answer is 3^6, you are in fact suggesting that painting the front of the cube black and everything else white is different from painting the bottom of the cube black and everything else white, when in fact you can simply rotate the cube to reach the same thing. To answer the question, you need to consider the symmetric group of the cube (which has order 24), the fixed point set of each element in the group, and then use the Cauchy-Frobenius-Burnside Theorem to count all possible paintings. The answer for three different colors is indeed 57.
I got 57 by using color combinations and spatial recognition without the need to learn Burnside's theorem and group theory.
1. All 6 faces are painted with only one color, red, blue, or green. There are obviously 3 ways total in this group.
2. All 6 faces are painted with two and only two colors. There are apparently 3 2-color combinations: red and blue, red and green, and blue and green. For each 2-color combination, there are 5 sub-combinations, for instance for red and blue combination, they are 1r5b, 2r4b, 3r3b, 4r2b, and 5r1b. The number of ways to paint the cube in these sub-combinations is 1, 2, 2, 2, and 1, respectively. The total number of ways stands at 3 x 8 = 24.
3. All 6 faces are painted with three colors. There are three combinations for these 6 faces to be painted in terms of number of faces painted by each color: 1, 1, 4; 1, 2, 3; and 2, 2, 2. For 1, 1, 4, it could be 1r, 1b, 4g, or 1r, 1g, 4b, or 1b, 1g, 4r, 3 sub-combinations. In each sub-combination, there are 2 ways to paint the cube and the total is 3 x 2 = 6. For 1, 2, 3, there are 6 sub-combinations, namely 1r2b3g, or 1r2g3b, or 1b2r3g, or 1b2g3r, or 1g2r3b, or 1g2b3r. In each sub-combination, there are 3 ways to paint the cube and so the total is 6 x 3 = 18. For 2r, 2b, 2g, there are 6 ways to paint the cube.
Eventually, there are a total of 3 + 24 + 6 + 18 + 6 = 57 distinct ways to paint the cube considering rotational symmetry.
With this method, you can get the answers for many questions framed differently, like "how many ways can you paint the cube with 3 colors when each color must be used for at least one face?".
This is a problem requiring the use of Burnside's lemma. You consider
- pornstar January 26, 2010the 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 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 and 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