Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Last night, a friend of mine informed me that there were forty-three quintillion positions that a Rubik's Cube could be in and asked me how many there were for my Professor's Cube (5x5x5).

So I gave him an upper bound:

$$8!~3^8\cdot24!~2^{24}/2^{12}\cdot12!~2^{12}\cdot24!/4!^6\cdot24!/4!^6,$$

did some rough approximation, and said it was around 10^79.

Then I decided I'd try to give a lower bound, and came up dry.

In the Wikipedia article, we read that:

  • The orientation of the eighth vertex depends on the other seven.
  • The 24 edge pieces that are next to vertices can't be flipped.
  • The twelfth central edge's orientation depends on the other eleven.
  • The parity of a permutation of the vertices and of the edge pieces are linked.

The second point is easy to see by imagining the route that such an edge piece takes under all the various moves. (The Wikipedia article opts to give a mechanical reason instead, which is a questionable practice.) The other points are not too hard to see either.

So we divide by $3\cdot2^{24}\cdot2\cdot2$ and get the answer, around $2.83\cdot10^{74}.$

My friend does not know group theory, and the only proof I know of the independence of the rest of the stuff uses group theory to a considerably greater extent than that which proves the dependent parts dependent. Can anyone think of a simpler proof of a reasonable lower bound? One that, say, at least puts the number greater than that for Rubik's Revenge (4x4x4), which is about $7.40\cdot10^{45}$?

share|improve this question
add comment

2 Answers

up vote 1 down vote accepted

The lower bound you get is actually the exact number of reachable different-looking configurations. I'd write it as $$ \frac{8! \cdot 24! \cdot 12!}{2} \cdot 3^7\cdot 2^{11}\cdot \frac{24!}{4!^6} \cdot \frac{24!}{4!^6} $$ The first factor counts the number of reachable permutations of the non-center cubies, ignoring orientation. The two middle ones count the number of possible orientations for the corners and central edges. Finally the last ones count the number of distinguishable states for each of the two sets of 24 movable center panels.

In order to see that this many different arrangements are actually possible, we can observe:

  • Of course the 8 corners are all different, as are the 12 central edges.

  • The 24 non-central edge pieces are all different, when we take into account that the outer end of such a piece stays the outer end no matter how we twist the cube. So seen from that end of the edge it has a distinct left and right face, and the colors of these two faces determine which piece it is.

So the two denominators of $4!^6$ for the center panels is all that is needed to take into account states that look the same but actually have physical pieces switched around. (By ignoring the middle centers completely in the count, we're implicitly taking account of the fact that they look the same in all four orientations).

So all that is needed is to convince ourselves that we can actually get to each of the positions we have counted, starting with a solved cube.

First get the $24!$ factor done with by moving the non-middle edges around such that each of them is next to the corner piece we want them to end up next to, and on the right side of it. During this phase the corner pieces themselves make no net movement. We don't care what happens to the middle edges or center pieces in this phase, so we can treat the cube as a 4×4×4 one with an irrelevant middle layer sandwiched into each dimension. Getting the non-center edges into place can be done with the 4×4×4 combination for flipping two neighbor edges together, and appropriate adaptations of that. (Here "adaptation" means "do something that brings the two edges you want to swap next to each other, not caring about anything else, then swap them, and finally do the initial something backwards").

Next get the the corners and the middle edges into the desired positions. If we work with only the two middle ones of the four cuts in each dimension, the cube will work like a plain old 3×3×3, and the non-middle edges will stay next to the corners we've just anchored them to. So the number of choices we have in this phase is exactly the number of positions on a 3×3×3 cube, namely $\frac{8!\cdot 12!}{2}3^7 2^{11}$.

In the first two phases we haven't cared about getting the center panels scrambled, but now finally handle the two factors of $\frac{24!}{4!^6}$ one by one by arranging each group of 24 center tiles as we want them. For each such group, there's a combination that cyclically permutes three centers pieces on different sides without touching anything else on the cube. Again, appropriate adaptations of this will allow us to do anything -- officially 3-cycles are not enough to do everything, but in pinch we can make the 3-cycle look like a plain swap of two pieces by choosing two of the three participants to be positions that are already of the same color, and plain swaps are (of course) enough to reach any desired pattern.

There's some tiny amount of group theory hidden in the talk about which permutations can be built up from which pieces, but it doesn't need to be phrased in those terms because the point is just that transpositions are enough to do everything. We don't need to tell that the "adaptations" of the basic operations I describe would be called conjugations by a group theorist, and we certainly don't need to mention that, say, the basic 3-cycle of center panels is constructed as a commutator.

(Note that this would be horribly slow as an actual solution algorithm, since it's optimized for making clear in a uniform way that all the states we've counted can be produced reachable).

share|improve this answer
add comment

Chris Hardwick has come up with a closed-form solution for the number of permutations for an $n\times n\times n$ cube: http://speedcubing.com/chris/cubecombos.html

share|improve this answer
    
I imagine the solution uses some group theory. –  Daniel Briggs Jan 16 '13 at 23:09
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.