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.

If I were to represent a state in the Rubik cube as a permutation of the colors on the 9 tiles per side on all sides of the cube, could I reach all possible states (i.e. colorings) by the permutations allowed by the cube alone? In other words, is there a legal coloring such that it's unreachable from the initial state (every side of the cube has only its own distinct color) ?

many thanks!

share|improve this question
1  
The answer is no; a common trick is to forcefully flip one corner of the cube, rendering in unsolvable, without the owner of the cube paying attention. However, I don't know how to prove it is indeed impossible to fix this by legal moves. –  Gadi A Sep 14 '11 at 10:32
4  
What do you mean by "legal coloring"? It is well known that the coloring reachable by the usual allowed moves is strictly smaller than the number of permutations obtainable by "taking apart the cube and re-assembling it", which is again smaller than the number of permutations obtainable by "removing the stickers and putting them back on". –  Willie Wong Sep 14 '11 at 10:34
2  
@Gadi and Dan: you may be interested in math.harvard.edu/~jjchen/docs/… especially Chapter 11. –  Willie Wong Sep 14 '11 at 10:44
    
@Willie: by legal I mean that for a 3x3x3 cube there are exactly 9 tiles with the same color, and there are 6 different colors. –  Dan Sep 14 '11 at 10:55
    
@Gadi: thanks for the comment, but I was hoping for a proof. –  Dan Sep 14 '11 at 10:56

2 Answers 2

up vote 7 down vote accepted

There are different ways of defining "legal".

In a comment, the OP posits that legal could mean

by legal I mean that for a 3x3x3 cube there are exactly 9 tiles with the same color, and there are 6 different colors.

In which case the existence of "legal" colorings not reachable by standard Rubik's cube moves is trivial: observe that a Rubik's cube move only sends

  • Corner pieces to corner pieces
  • Center pieces to center pieces
  • Edge pieces to edge pieces

So if you peel of the Red center piece sticker and swap it with the sticker of a blue edge piece, you will still have 9 "red tiles", but no "red center tile", so it cannot be arrived at by a standard permutation.

Okay so perhaps you want to strengthen the condition on the tiles. May be we amend the definition of legal to be

A color configuration is legal if there are 6 total colors, each color has 9 tiles, and of the 9 tiles you have 1 center piece, 4 corner pieces, and 4 edge pieces.

This is still not sufficient to guarantee that the cube is solvable. One property of the standard Rubik's cube moves is that opposite centers can never be made adjacent. So take a solved standard cube, with (assuming) white being the top face, blue being the bottom face, and red being a side face. If you take an arbitrary edge sticker off the blue side, and swap it with the red edge sticker that is adjacent to the white face you've created an impossible cube, because the cube now has an edge face with white/blue, but white and blue centers can never be adjacent.

So okay, that is still a trivial impossibility. Perhaps we need to strengthen our definitions even more. The next natural assumption is then

In a solved cube there are 12 edges and 8 corners. Each edge has two colors. Each corner has 3. We say a color configuration is "legal" if it has 6 total colors, 9 tiles of each color, with 1 in the center, 4 on the edge, and 4 on the corner. Furthermore, we require that the color combinations for the edges and corners are in one-to-one correspondence with those available on a solved cube.

In fact, this turns out to be what I call the "take the cube apart and reassemble" definition. (You'll know what I mean if you've ever tried taking apart a Rubik's cube.)

In this situation there are still impossible configurations: for example, if you pry off one single edge piece and re-insert it "upside down". The proof that such configurations are impossible is more difficult, and requires learning some group theory. (See chapter 11 of this exposition.) But the fundamental idea behind the argument is same as the previous cases: one needs to find "algebraic invariants" which describe the configuration of the cube, and which values are left unchanged by the Rubik's cube moves. By constructing a configuration with a different value for the invariants compared to the solved cube, you obtain an example that can be demonstrated to not be solvable.

In the first example, the algebraic invariants are the "number of edge/center/corner tiles per color". In the second example, the algebraic invariants are "the number of edges shared by two given colors". For the third example, I invite you to read the linked PDF file.

share|improve this answer
1  
about "the proof that such configurations are impossible is more difficult", once the invariants are defined it is easy to check that a quarter-turn of one face (and thus any move) does not change them. What is much harder is to show that any position satisfying all the constraints can in fact be reached. That is equivalent to providing a solution algorithm for the Rubik's cube. –  zyx Sep 14 '11 at 12:25
    
@zyx While in practice it's (roughly) equivalent to providing a solution algorithm, I'd argue that there are 'non-constructive' proofs showing that any satisfying position can be reached; that is, proofs that give no explicit algorithm. Since we're dealing with a finite object, obviously all possible move strings could be tried, but for instance there may be easy proofs that positions are reachable that don't lead to polynomial-time solving algorithms... –  Steven Stadnicki Sep 14 '11 at 15:41
    
(With 'polynomial-time' obviously implying that we allow the cube to get bigger than 3x3x3, I suppose!) –  Steven Stadnicki Sep 14 '11 at 15:42

If I remember correctly, 1/6 of the permutations are reachable. The total edge parity (mod 2) and corner twisting (mod 3) have to be the same as the starting position.

Edit: according to the document linked in the comments under the question there is an additional parity condition, and the fraction of reachable positions is 1/12.

share|improve this answer
    
depending on how you define permutations, it could be much less even. The usual definitions give the numbers you wrote, but if you allow "peeling sticker" type of permutations, the space of configurations get a lot larger. –  Willie Wong Sep 14 '11 at 11:50
1  
@Willie: also, the analysis is a bit different for non-uniform colorings of the faces, as in the cubes with a photograph imprinted on each side. This produces a "center torsion" mod 4 invariant and possibly other conditions relating its value to the edge and corner torsion. –  zyx Sep 14 '11 at 12:05

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.