Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Imagine an $n \times n \times n$ Rubik's cube, where we can transition the state of the cube using Singmaster moves under either the face- or quarter-turn metrics. We call a face of this cube "solved" if all of the symbols on the face are of the same color (there are six total colors).

How many total cube states are there when $k = {0, 1, 2, 3, 4}$ of the cube faces are solved, and what "distribution" are these states drawn from? Namely, what is the probability that they contain the fully solved state of the cube? Is this probability what one would expect for a uniform random sampling from the set of all possible cube states?

Note: This is (hopefully) a simplification of an earlier question asking for the probability that a greedy algorithm solves a Rubik's cube, where once a face is solved, the algorithm cannot backtrack and perturb the face (though rotations of the face are allowed).

Note 2: I know there are only going to be a small number of possible cube states when we freeze a face. Exact counts would be fantastic, but my goal here is to understand what distribution they are being drawn from.

share|improve this question
1  
I can do the cases $k=6$ and $k=5$...! –  Greg Martin Dec 20 '12 at 8:06
    
@Greg Martin :) –  FloatingForest Dec 20 '12 at 10:06
    
If you really fix one face then it will be hard to solve the cube :) –  François Brunault Dec 20 '12 at 12:32
    
@Francois Brunault I'm looking to make a statement of just how frequently you can solve the cube when you fix one or more faces. The answer, no doubt, will be "very infrequently". –  FloatingForest Dec 20 '12 at 12:39
    
There are two interpretations. (1) For $k$ colours, there are $k$ monochromatic faces of the cube. (2) The 9 squares of each of the $k$ colours are in exactly the positions they hold in some complete solution. Version (2) is a point-wise stabiliser problem that any group package should be able to answer. Version (1) is a bit tricker (unless it can be proved that it is really the same). –  Brendan McKay Dec 20 '12 at 13:03
show 10 more comments

Your Answer

 
discard

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

Browse other questions tagged or ask your own question.