Is there a state in Rubik's cube which can be considered to have the highest degree of randomness (maximum entropy?) asssuming that the solved Rubik's cube has the lowest?
- Anybody can ask a question
- Anybody can answer
- The best answers are voted up and rise to the top
Assuming 'most random' means 'takes the most number of moves to solve the cube', then the answer is 20. This site also has an example of a state that requires at least 20 moves to solve. This result is from 2010, and is a computer-assisted proof.
Just as shuffling a deck of cards several times (say 7 or more) gives a very good approximation of a randomly chosen ordering of cards, mixing up a cube with 50 or 60 turns will give a very good approximation of a randomly chosen cube state.
A randomly chosen cube state might be what you want-- there is no single "most random" state. If there were, then in some sense, it wouldn't be very random; it would be very special! However, if you take a randomly chosen cube state, there's over a 99.75% chance it is at least 16 moves away from being solved; so we expect a randomly chosen cube to be very far away from a solved one.
Yes, it's possible to randomly mix up a cube and end up with something only a few moves from a solved cube, or even to end up with a perfectly solved cube. But the odds against it are astronomical. You could shuffle cards until the sun burns out (~5 billion years), and it's unlikely you would have put them back in order even once. Likewise, you could jumble the cube until the sun burns out, it's unlikely you'll just happen to solve the cube in all that time.
The nice thing about a randomly chosen state is that it's easy to approximate-- just randomly make turns for a while. I don't know how many turns you should do, I would guess 60 turns is plenty. I've seen people spend a long time, doing hundreds and hundreds of turns, trying to make the cube really hard to solve-- but all those extra turns don't accomplish much, it's still just another randomly chosen cube state, and we expect it to be just as hard to solve.
If you're considering maximal entropy as I think your question alludes to, you need to maximize the degeneracy of the states since $S \equiv k \ln \Omega$, where $\Omega$ is the number microstates.
It doesn't make sense to consider a single state of the cube to be most random...we could just as well consider our chosen state to be "solved" and that would make it the least "random" in that sense. It makes more sense to consider an ensemble of cubes to be the most random state. In this case, the ensemble of cubes with the highest degeneracy is 18 moves away from being solved, with degeneracy of roughly 29 quintillion.