Rubik's Cube Permutations
Q: If a monkey was playing with the Rubik's Cube what would be the odds of him solving it when he was done playing?
A: The six center faces of the cube are fixed. By turning the faces all you can do is rearrange the corners and edges. If you could take the cube part there would be 8!=40,320 ways to arrange the eight corners, without respect to the orientation of each piece. Likewise there are 12!=479,001,600 ways to arrange the 12 edges without regard to orientation.
There are 3 ways each corner can be oriented, for a total of 3^8=6,561 corner orientations. Likewise there are two ways each edge piece can be oriented, for a total of 2^12=4,096 edge orientations.
If we could take the cube apart, and rearrange the edge and corner groups, then there would be 8! × 12! × 3^8 × 2^12 = 519,024,039,293,878,000,000 possible permutations. However, not all of these permutations can be arrived at by rotating the faces.
First, it is impossible to rotate just one corner and leave everything else the same. No combination of turns will achieve that. Basically, every action has to have a reaction. If you wish to rotate one corner it would disturb the other pieces somehow. Likewise, it is impossible to flop just one edge piece. For these reasons we have to divide the number of permutations by 3 × 2 = 6.
Third, it is impossible to switch two edge pieces without disturbing the rest of the cube. This is the hardest part of this answer to explain why. All you can do with a Rubik's Cube is rotate one face at a time. Each movement rotates four edge pieces and four corner pieces for a total of eight pieces moved. A sequence of rotations can be represented by a number of piece movements divisible by 8. Often a sequence of moves will result in two movements canceling each other out. However, there will always be an even number of pieces moved with any sequence of rotations. To swap two edge pieces would be one movement, an odd number, which can not be achieved with the sum of any set of even numbers. Mathematicians would call this a parity problem. So we have to divide by another 2 because two edge pieces cannot be swapped without other pieces being disturbed.
So there are 3 × 2 × 2 = 12 possible groups of Rubik's Cube permutations. If you disassembled your brother's Rubik's Cube and put it back together randomly, there is a 1 in 12 chance that it would be solvable. So the total number of permutations in a Rubik's Cube is be 8! × 12! × 3^8 × 2^12 / 12 = 43,252,003,274,489,900,000. If you had seven billion monkeys, about the human world population, playing randomly with the Rubik's cube, at a rate of one rotation per second, it would take 196 years on average for a cube to be solved for just one second.
I also like monkeys.
Man, I wouldn't want to be there when they get frustrated and do what 7 billion monkeys do when they get frustrated.Quote: WizardIf you had seven billion monkeys, about the human world population, playing randomly with the Rubik's cube, at a rate of one rotation per second, it would take 196 years on average for a cube to be solved for just one second.
The wording of the last statement is confusing. Try: ...about once every 196 years, one cube will be in the correct solved pattern, for one second.
Other than that, it seems good.
After the paragraph on how the cube works, do the "possible" math. Explain how that works and how long it would take the roomful of monkeys to solve a cube.
Finally, explain that people get it wrong if they guess the 519 Quintillion (If I am reading it right) permutations because they do not take into account how a cube works.
Just my $.02.
Quote: WizardHere is a draft of a Q&A from my next "Ask the Wizard" column. I know I have the answer right, but I don't know if my explanation of the parity issue is either clear or correct. I've seen discussions of it online, and they always seem to require many pages of difficult group theory to explain it. I'm trying to boil it down to plain simple English. What do you think?
Q: If a monkey was playing with the Rubik's Cube what would be the odds of him solving it when he was done playing?
A: [long math answer snipped]
I think the question is indeterminate. "When he was done playing" is undefined, and without a proper stopping criteria you can't answer the question. You could answer alternate questions like
Q1: "Given a randomly-perturbed Rubik's Cube, on average how many additional random perturbations would be required to reach the solved state?"
or
Q2: "Given a randomly-perturbed Rubik's Cube, what is the probability of the cube being in the solved state after exactly N additional random perturbations?"
I tend to think the original question is really getting at Q2, but if the "when he was done playing" condition is (circularly) defined as having solved the cube, the probability is 1.0. He'll get there eventually, because unless the cube has been disassembled and reassembled improperly, each cube can be solved.
I still have a 1980s Rubik's cube on my shelf. It's in the solved configuration, and I haven't dared to alter it in decades. I didn't completely follow parts of your explanation, but that says much more about my relationship with a Rubik's cube than it does about your explanation.
Quote: DJTeddyBearMan, I wouldn't want to be there when they get frustrated and do what 7 billion monkeys do when they get frustrated.
The wording of the last statement is confusing. Try: ...about once every 196 years, one cube will be in the correct solved pattern, for one second.
I would just drop the part about being correct "for one second." It isn't really needed and not what people are thinking when they think of a problem like this. Just state it like, "It would take 7 billion monkeys 196 years to solve one cube."
This just hit me, and I really hate to bring it up in a way, but your answer seems to assume the monkeys need to hit every possible permutation before solving the cube. Isn't the probability of a perfectly solved cube the same as the probability of any other random pattern and thus the monkeys don't need to make every combination before hitting the "perfect" one?
I recall playing with the damned things. I learned to "solve" up to three faces on my own, but like most everyone else I needed help in solving the whole cube. The easiest solution is to dissasemble it and put it together again in the right way, and I don't think that's cheating ;)
Quote: NareedA monkey's more likely to smash it than to solve it.
I recall playing with the damned things. I learned to "solve" up to three faces on my own, but like most everyone else I needed help in solving the whole cube. The easiest solution is to dissasemble it and put it together again in the right way, and I don't think that's cheating ;)
I always thought the easiest way was to solve as much as possible, then change the last few stickers around.
But the explanation essentially works for me.
Quote: CroupierI always thought the easiest way was to solve as much as possible, then change the last few stickers around.
But the explanation essentially works for me.
Oh, no. You can ruin the stickers if you remove them. I know people who did that, and others who painted them over.
To take it apart you just sitck a key or a screwdriver in one of the center pieces on the edge and pop it loose. The rest come loose easily after that, and you just put it back the way you want. The pieces just snap back into place.
"For one second" is important because a monkey wouldn't recognize when he's done.Quote: AZDuffmanQuote: DJTeddyBearMan, I wouldn't want to be there when they get frustrated and do what 7 billion monkeys do when they get frustrated.
The wording of the last statement is confusing. Try: ...about once every 196 years, one cube will be in the correct solved pattern, for one second.
I would just drop the part about being correct "for one second." It isn't really needed and not what people are thinking when they think of a problem like this. Just state it like, "It would take 7 billion monkeys 196 years to solve one cube."
This just hit me, and I really hate to bring it up in a way, but your answer seems to assume the monkeys need to hit every possible permutation before solving the cube. Isn't the probability of a perfectly solved cube the same as the probability of any other random pattern and thus the monkeys don't need to make every combination before hitting the "perfect" one?
On that note, a money wouldn't recognize that he's cycling thru just a couple combinations either....
Quite frankly, I'd get rid of the entire monkey analogy and simply state how many different ways the 6 faces can be organized.
The cause & effect explaination is good, but get rid of the monkeys.
Quote: AZDuffmanI would just drop the part about being correct "for one second." It isn't really needed and not what people are thinking when they think of a problem like this. Just state it like, "It would take 7 billion monkeys 196 years to solve one cube."
What I'm trying to get at is once every 196 years on average there will be somewhere on earth a solved Rubik's Cube. This will happen for just one second and then the monkey will mess it up. I don't want the reader to have the mental image that after exactly 196 years there will be a cube in the solved position, which would imply a probability of 1 in 7 billion. I'm open to how to word this.
I agree that if you wanted to cheat, the best way would be to get a screwdriver and pop off a piece, preferably an edge piece. Then the rest of the cube will fall apart. Then put it back together in the solved position. You'll have to be forceful to get the last piece in. One you remove the stickers they will never lay nice and flat again.
Quote: WizardI agree that if you wanted to cheat, the best way would be to get a screwdriver and pop off a piece, preferably an edge piece.
I disagree that it is cheating. After all, it is a solution to get the pieces back to their original configuration. It would be cheating in a competition (and would probably lose anyway, I've seen people solve random cubes in under 30 seconds)
Quote: DJTeddyBearMan, I wouldn't want to be there when they get frustrated and do what 7 billion monkeys do when they get frustrated.
The wording of the last statement is confusing. Try: ...about once every 196 years, one cube will be in the correct solved pattern, for one second.
Other than that, it seems good.
Yeah, because the monkey could have solved it, but kept playing, and then stopped with it unsolved.
Quote: NareedHow's this for a coincidence? On the way out to lunch an hour ago, I saw the security guard playing with a Rubik's cube! I hadn't seen one in years.
Just out of curiosity, is your security guard also a monkey? because that would be an amazing coincidence.
Quote: CroupierJust out of curiosity, is your security guard also a monkey? because that would be an amazing coincidence.
Actually you'd get in trouble if you called him that ;)
Quote: NareedActually you'd get in trouble if you called him that ;)
Oops. I was using the joke more as an indictment of the mental acuity of a lot of the security guards I know. Seems less funny now.
Quote: CroupierOops. I was using the joke more as an indictment of the mental acuity of a lot of the security guards I know. Seems less funny now.
No, no. People are so sensitive these days. I meant the man might take offense and beat the living daylights out of you (whatever that means). Nothing more than that.
Let's agree on something, if you see a smiley at the end of a sentence, that means I'm joking. Ok?
Quote: NareedNo, no. People are so sensitive these days. I meant the man might take offense and beat the living daylights out of you (whatever that means). Nothing more than that.
Let's agree on something, if you see a smiley at the end of a sentence, that means I'm joking. Ok?
I have got a better idea. I will just stop posting while drunk.
Quote: CroupierJust out of curiosity, is your security guard also a monkey? because that would be an amazing coincidence.
I thought that was very funny. You should get drunk and post more often.
I think the Wizard's explanation is good. 7 billion monkeys making a turn every second would take on average 196 years to have a solution that would last for 1 second. Pretty crazy.
However, a Rubik's cube is solvable from any state in 20 moves. This is called "God's number". What are the odds that a monkey would solve a cube in 20 moves?
Quote: boymimboHowever, a Rubik's cube is solvable from any state in 20 moves. This is called "God's number". What are the odds that a monkey would solve a cube in 20 moves?
There are 43,252,003,274,489,900,000 permutations.
There are 18 possible rotations: 6 faces by 3 degrees of rotation (90, 180, and 270).
If this were like trying to crack a code where each digit had 18 possibilities, and there were 43,252,003,274,489,900,000 possible combinations, then you would need 15.64 digits. So the 20 moves seems mathematically reasonable to me. However, as one who used to be able to solve the cube in under a minute, that seems incredible. I estimate it took me an average of 150-200 moves to solve it.
By the way, in high school I could solve the cube with only my feet.
Quote: Wizard... By the way, in high school I could solve the cube with only my feet.
Now I understand the basis for the "monkeys" aspect of the Q&A.
Quote: DocNow I understand the basis for the "monkeys" aspect of the Q&A.
Ouch! Well played, Doc.
Quote: WizardThere are 43,252,003,274,489,900,000 permutations.
There are 18 possible rotations: 6 faces by 3 degrees of rotation (90, 180, and 270).
If this were like trying to crack a code where each digit had 18 possibilities, and there were 43,252,003,274,489,900,000 possible combinations, then you would need 15.64 digits. So the 20 moves seems mathematically reasonable to me. However, as one who used to be able to solve the cube in under a minute, that seems incredible. I estimate it took me an average of 150-200 moves to solve it.
By the way, in high school I could solve the cube with only my feet.
This is a link to a website with an interesting breakdown of how the "solve from any position in 20 moves or less" algorithim was developed. Basically, it appears that they got 7 billion monkeys and put all their moves into a super computer. According to the website, there are only 300,000,000 permutations that require 20 moves. All the others can be solved in less.
