Monday 8 February 2016

calculation puzzle - How many distinct unsolvable Rubik's cubes exist?


I wanted to answer this question:


Why can't I have only one edge piece flipped on a 3X3 Rubik's cube?


by saying that it is homomorphic to the illegal state in this question:


Why is a single-corner twist not a valid position on a Rubik's cube?


That does not appear to be nessesarily true. A more interesting question than either of them is, therefore:



If I were to break apart, put back together randomly, and try to solve my Rubik's cube, what is the probability that the resulting cube is solvable?



If there are only 2 homomorphs, the answer should be $50\%$. If there are more....



I am inclined to believe there are more than 2 (at least 6) as if you rotate a corner, there are 3 different orientations that cannot be alternated.



Answer



My answer at Why is a single-corner twist not a valid position on a Rubik's cube? basically explains this, but in simpler terminology here are the facts presented without proof.


If you randomly disassemble and reassemble a $3 \times 3 \times 3$ cube, the probability that it will be solvable with just face turns is exactly $1 \over 12$. Furthermore, this number has a simple interpretation.


Any random state of the cube can be reduced with only face turns to one of these 12 configurations. Furthermore, none of these configurations can be achieved from any other one with solely face turns.


12 configurations image


The pattern here is pretty simple. Going from left to right is just twisting a corner (in this case the yellow-blue-red one). Going up or down by 2 rows is flipping an edge (in this case the yellow-green one). Going between the 1st and 2nd or 3rd and 4th rows is swapping 2 edges (in this case the yellow-orange and yellow-red ones).


The set of all states which can be reduced to one of these 12 configurations is called an "orbit", and each of these 12 orbits has the same number of states as the others (which is basically Lagrange's theorem). Thus, each has exactly $1 \over 12$ of all states.


Notice that the upper left corner is the solved cube. The orbit of this cube is exactly the set of states you can solve just with face turns. Since it has $1 \over 12 $ of all the possible states, the probability that a randomly reassembled cube will be solvable is exactly ${1 \over 12} \approx 8.3\% $. The other ${11 \over 12} \approx 91.7 \% $ of the time, you'll end up in a different orbit, and eventually reach one of the other states above, at which point you can't solve it any further without face turns.


No comments:

Post a Comment

Understanding Stagnation point in pitot fluid

What is stagnation point in fluid mechanics. At the open end of the pitot tube the velocity of the fluid becomes zero.But that should result...