The Unapologetic Mathematician

Mathematics for the interested outsider

Rubik’s Magic Cube

Rubik’s Cube is a classic fad from the ’80s. Invented by architecture professor Ernő Rubik in 1974 as an illustration of design principles, it became an immensely popular puzzle for a while. Now it’s a hallmark of geekiness — when I visited Dartmouth I saw at least six or seven floating around the graduate student lounge.

What’s most interesting to us here is that it’s also a big case study in group theory. The official website has a pretty good Java implementation, for those who don’t remember (or who have repressed their memories of) the cube. I’ll start talking about the cube after the jump.

The cube is broken into 27 small “cubies”. There are eight corner cubies with three colors on each, twelve edge cubies with two colors each, six face cubies with one color each, and a single central cubie hidden in the middle of the cube. We can shuffle around the corners in 8! (8*7*6*5*4*3*2*1) ways, and rotate each corner three ways. We can shuffle the edges 12! ways and flip each one two ways. We’ll consider the faces of the cube to be fixed in place, providing an orientating framework that the edges and corners can move around. That means we have a total of 12!*212*8!*38 = 519,024,039,293,878,272,000 different states of the cube. Rotating a side of the cube shuffles around these states, so the six different rotations generate a group F_6 acting on the set of states! Not all such transformations are distinct, though. Rotating the same side four times in a row always brings us back where we started. In fact, there’s a normal subgroup N of sequences of rotations that always bring us back where we started. The group F_6 of all sequences of rotations modulo the subgroup N of “trivial” transformations is the Rubik’s Group G.

Now, Rubik’s group can’t send every state to every other state. There are three pieces of data about the state of the cube that every member of G leaves the same. We can’t rotate a single corner cubie and leave everything else the same, we can’t flip a single edge cubie and leave everything else the same, and the permutations of the corners and the edges are either both even or both odd (remember what we mean by “even” and “odd” permutations). I’ll prove the last one here.

For the moment, forget about the orientation of each cubie. Just think about the space around the cube that it occupies — its “cubicle”. Now think of rotating one side. This takes the four corners on that side and cycles them around, and also takes the four edges on that side and cycles them around. Remember that a four-cycle is an odd permutation, so rotating a side of the cube gives an odd permutation of both corners and edges. Every time we do another rotation we do another odd permutation on each set of cubies, so after n rotations we either have both even permutations (if n is even) or both odd permutations (if n is odd). We just can’t do an even permutation of edges and an odd permutation of corners.

So, the restriction on corner orientations cuts down the states we can reach by a factor of 3, the restriction on the edge orientations gives a factor of 2, and the restriction on the signs of the permutations gives another factor of 2. It turns out that everything else is a possible transformation, which I’ll try to prove eventually. This means that the set of all states consists of 12 orbits, each containing 43,252,003,274,489,856,000 states.

Rubik’s Group also has 43,252,003,274,489,856,000 elements. To see this, notice that no two elements of the group can induce the same transformation of states. If we have sequences of rotations g and h that both act on the set of states the same way, then gh^{-1} would send every state back to itself, meaning that this composition of rotations lives in the subgroup N. But that means that gh^{-1} is the identity in Rubik’s Group G (the quotient of all rotation sequences by N) so g and h are the same in G. Given two states in an orbit there’s exactly one way (modulo N) to get from one to the other, so G has 43,252,003,274,489,856,000 elements.

I’ll be writing more about this in later posts as more and more tools of group theory come into our grasp. For now, I’ll end with a little note about how truly ginormous this number is. The marketing department back when Rubik’s Cube was first sold slapped a note on each package saying “more than 2 billion possible combinations”. In fact, there are more than twenty billion times more. To get a grasp on this sort of magnitude, remember the McDonalds’ signs that used to count up to “over 99 billion served”. Imagine changing that to “over 5 served”. That’s how far they underrated the number of states of the cube. And yet I hope to show that using group theory we can tame this hugely complicated beast and understand not only how to solve the cube, but why our solutions work.

About these ads

February 22, 2007 - Posted by | Group theory, Rubik\'s Cube

15 Comments »

  1. [...] So the second Carnival of Mathematics is up at Good Math, Bad Math. My first post on Rubik’s Cube is up there, as well as one about algebraic topology at UM regular Mikael [...]

    Pingback by Carny Folk « The Unapologetic Mathematician | February 23, 2007 | Reply

  2. Any addenda on the group order of the 4-dimensional and 5-dimensional Rubik’s Hypercubes that have been solved by simulation?

    Comment by Jonathan Vos Post | February 26, 2007 | Reply

  3. Oh this is only the first post about the Cube. Just you wait.

    Comment by John Armstrong | February 26, 2007 | Reply

  4. [...] of Rubik’s Group Today I’m going to prove the other two constraints I mentioned in the first post about Rubik’s Group: the total corner twist and the total edge flip must both be [...]

    Pingback by Restrictions of Rubik’s Group « The Unapologetic Mathematician | March 7, 2007 | Reply

  5. [...] all the structure I’m talking about. Specifically, it’s a subgroup of the bigger group I mentioned back at the beginning. We can restate the three restrictions as saying the maneuvers in Rubik’s group are those in [...]

    Pingback by Rubik's Cube Wrapup « The Unapologetic Mathematician | March 28, 2007 | Reply

  6. I read the same comparison of Mac Donald’s and Rubik’s cube number of permutations in a PDF document:

    http://www.geometer.org/rubik/index.html

    Click in “Group Theory via Rubik’s Cube”

    Who said this first?

    Comment by Herman Jaramillo | July 18, 2007 | Reply

  7. Herman, I don’t know whether the author of that document wrote it before or after I wrote this page. That sort of comparison was common enough back in the 1980s, though. I think I first saw it in Christoph Bandelow’s Inside the Rubik’s Cube and Beyond, and it may have been mentioned in John Allen Paulos’ Innumeracy. Of course, back then McDonalds was only on about 40 billion, so the statement was generally rendered, “more than 2 served”.

    Comment by John Armstrong | July 18, 2007 | Reply

  8. [...] number of points in the orbit of is is the number of elements of . We saw such a free action of Rubik’s Group, which is why every orbit of the group in the set of states of the cube has the same [...]

    Pingback by A few more facts about group actions « The Unapologetic Mathematician | March 6, 2008 | Reply

  9. Very interesting article, thanks for posting! I was wondering if you could explain farther the concept of the 12 orbits? I don’t understand completely that part.

    Comment by Ariana de los Cobos | May 15, 2013 | Reply

  10. Ariana, the basic idea is that if you take the cube apart and put it back together randomly, there is only a 1/12 chance that you will be able to solve the resulting state with normal layer-turning moves. For example, if you twist a single corner on its own, there is no way to undo that with layer-turns. Since there are three ways to turn a corner — leave it alone, turn it 1/3 to the right, and turn it 1/3 to the left — this accounts for three separate “orbits”. None of the states you can reach from any of those three positions of the corner will overlap.

    Comment by John Armstrong | May 15, 2013 | Reply

  11. Thanks for such a quick reply, John. I think I’m beginning to comprehend… but, if I understand correctly, there are three separate orbits for each corner cube. So, if there are 8 corner cubes with three separate orbits for each, there would be 24 orbits… so why 12?

    Also, why not take into account the edge cubes?

    Comment by Ariana de los Cobos | May 15, 2013 | Reply

  12. So, the problem is with twisting a single corner cube on its own. You can twist corners to the right (+1) or to the left (-1), but the total must add up to a multiple of three for the state to be solvable with layer-turns. Three corners to the right works; one to the right and one to the left works; two to the right doesn’t, but you can get from there to a state where a single corner has been twisted to the left (2 = -1 modulo 3).

    Why 12? Because the same thing is true about flipping a single edge on its own, which gives two orbits. And you can’t swap a single pair of corners or a single pair of edges; technically the “parity” of the corner permutation and edge permutation must be the same. This gives another two orbits, one where the parities match and one where they don’t. So 3 * 2 * 2 = 12.

    Comment by John Armstrong | May 15, 2013 | Reply

  13. I’m sorry, I don’t understand, exactly – I am doing a Maths IA (high school project) on this, which is why I am persistent on this.

    I understand the fact that flipping an edge cube gives two orbits and that flipping a corner cube can give three. However, I’m confused about the parity of the corner/edge cube permutations; does this mean that if we flipped around two corner cubes, the number of orbits possible would still be the same?

    Comment by Ariana de los Cobos | May 16, 2013 | Reply

  14. Yes, that last one is sort of harder to get, but this is the condition that I explain more thoroughly in the post itself. It’s not about flipping or twisting an individual cube, but about swapping corner or edge cubes. For example, if you took out two edge cubes and swapped them (don’t worry about how they flip), you wouldn’t be able to solve the resulting state with layer-moves. Similarly, swapping just two corner cubes is impossible with only layer-moves. But you can swap a pair of each.

    Comment by John Armstrong | May 16, 2013 | Reply

  15. I understand, now – thank you so much!

    Comment by Ariana de los Cobos | June 23, 2013 | Reply


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 388 other followers

%d bloggers like this: