# What’s the Monkey number of the Rubik’s cube?

welcome to another mythology video today's video should be of interest to everybody who loves twisty puzzles as well as all hardcore mythology fans in 2010 30 years after the Rubik's Cube rocked the puzzle world it was finally

Proven that God's number for the Rubik's Cube is 20 what this means is that every single one of the 43 quintillion possible configurations of the Rubik's Cube can be solved with 20 or less turns now that's great but what other fun and

Challenging rubik's cube maths problems are there well there are a couple of closer related more or less open problems that I really like and that are not that well known to motivate these problems let me ask you to picture

Yourself scrambling a Rubik's Cube what are you doing there basically you're trying to turn yourself into a monkey performing random twists on the cube until it looks suitably scrambled this mental picture of a

Monkey messing around with a cube then raises a couple of very natural questions first question how many twists should the monkey execute to ensure that the cube is in a sufficiently random position so random now for example to

Create a fair starting position in a speed cubing competition second question suppose just for fun you enter a monkey in a speed cubing competition happens all the time right on average how many twists would it take

For the monkey to solve the cube now mythology is a very low-budget operation and we can only afford one monkey so the same monkey is both scrambling the cube and then unscrambling it this means our monkey begins and ends with a solved

Cube which motivates our third question if a monkey begins scrambling a solved cube on average how many twists will it take for the cube to be solved again on and off over the past couple of weeks I've been pondering these problems for

The Rubik's Cube and it's baby brother the tube – BRR – pocket cube I've been assisted by my new best friend computer whiz Eric Dominic from Switzerland let me tell you about some of the beautiful things we've

Discovered okay the first thing to realize about pretty much all metz problems to do with twisty puzzles is that they are finite in nature this means that it is usually pretty easy to come up with formulas or procedures that

Solve the problems for example to determine God's number for the Rubik's Cube in theory all you have to do is to figure out for every possible configuration what the least number of twists is to solve that configuration

Then God's number is simply the largest of all these numbers happens to be 20 but of course even if such a calculation is fine in theory in practice it would be truly horrendous even for a single configuration it's not that easy to

Calculate the minimum number of twists and of course they are ridiculously many configurations to consider so it's impossible to use this kind of straightforward brute force approach to calculate God's number unless of course

You've got God's computer same thing with our three monkey problems these sorts of problems are dealt with in general in the theories of sophistic processes Markov chains and random walks and there are theoretical solutions that

Deal with all three of them The Associated buzzwords are mixing time for problem 1 mean time from equilibrium for problem 2 and mean recurrence time for problem 3 however again because the complexity of the configuration space of

The Rubik's Cube using these formulas to find exact solutions to our problems appears impossible or at least very very very very very hard except there is a real surprise the third problem mean recurrence time has a very simple

Solution it turns out that the average number of twists a monkey needs to go from solved to solved is exactly equal to the number of configurations of the Rubik's Cube how cool and how surprising is that anyway

This solution to our third problem works for the three by three by three for the two by two by two and for many other twisty puzzles so for example in the case of the two bird who were two there are three million six hundred seventy

Four thousand one hundred sixty configurations and so it will take our monkey on average three million six hundred seventy four thousand one hundred sixty twists to stumble his way from solve to solved and for the three

By three by three it will take on average about 43 quintillion twists for those of you interested at the end of the video I'll sketch a really simple proof of this fact which applies to all sorts of other highly symmetric twisty

Puzzles and probabilistic experiments really a great thing to know but let's just continue with our story of discovery okay now this is the point where my new best friend Eric enters the picture among other things Eric he

Maintains a really fun web page on which he simulates the famous Infinite Monkey theorem this theorem says that if you have an immortal monkey type random letters on a typewriter then the monkey will almost certainly type out the

Complete works of Shakespeare and the Harry Potter books and any other book you care to choose you just have to be very very very very very very very patient eric has a couple of virtual monkeys typing away on his page and

Reports on anything reasonable the monkeys have produced anyway back to the cubes the first thing Eric and I tried was to test a theoretical result that I just mentioned so for the two by two by two we had a virtual slave monkey

Stumble from solve to solved over and over again our theoretical result says that the average number of twists required should approach three point six million and that was indeed the case for our virtual monkey what was particularly

Interesting was that we didn't have to wait very long for the correct average to roughly materialize just a couple hundred solves and ever settled down to approximately three point six million twists that gave us

Confidence in our computer implementation of the problem the next step was to attack our second problem so the monkey was to repeatedly start with a random configuration and to solve from there so we began by having the monkey

Execute a couple hundred random twists to hopefully give the monkey a random starting configuration and we then had the monkey begin solving with about the same number of solving sessions as before the average number of twists to

Solve the cube panned out to be around 4.5 million now a potential problem with this approach is that a couple of hundred random scrambling twists may not actually be enough to properly randomize the cube which brings us back to our

Problem one how many random twists are enough to randomize a Rubik's Cube well this is an extremely tricky question that is also of keen interest to real-life Cuba's it has been solved with an ingenious Gordian knot approach the

Word cubing Association which provides the scrambles for Cuban competitions actually doesn't use random twisting at all to create a two by two and three by three by three scrambles they used to execute 25 so-called non-redundant

Random twists for both the 2 by 2 by 2 and a 3 by 3 by 3 to randomize but they don't do this any longer what they do these days is to use a computer program called tea noodle which essentially does the following

It takes a cube explodes it and reassembles the pieces back into the cube completely randomly which is actually not a problem ok so now we have a truly random configuration unfortunately only 1/3 of the

Configurations that can be made this way can actually be solved by twisting the cube luckily there's a very easy test to check whether or not this is the case and I actually already described such a test in an earlier video and so to

Create a truly random solvable scramble the program just keeps exploring and reassembling cubes until a solvable configuration results neat isn't it actually I had a great discussion with Jeremy Fleischman and Lucas Guerin two

Of the speed cubers behind Tino and discovered that there's a whole video worth of material about how they make sure that the different kinds of twisty puzzle used in competitions are scrambled fairly I put some more info in

The description of this video so instead of just scrambling by twisting and hoping for the best we also ran our second experiment again using this confirmed totally random way of scrambling so with scrambled using

Exploring resembling and then had the monkey solve with random twists the result as far as we could tell was exactly the same as before so approximately 4.5 million twists on average great well not if you're the

Monkey now just for fun let's really enter our monkey into a speed cubing competition obviously computers are lot faster than humans at solving twisty puzzles so to give us humans fighting chance let's give the computer a bit of

A handicap let it solve our monkey ok so the god of speed cubing is Felix Zen Dex who just like me happens to live in Melbourne in Australia his best two times two times two time is 0.79 believe it or not seconds and his best three

Times three times three times is four point twenty two seconds I know completely insane right so how would Felix fare against one of Eric's monkeys on his best day okay first the two by two by two well eres

Monkeys scrambles at around 78,000 twists per second and so 4.5 million twists will take about 58 seconds and so unless the monkey gets very lucky he won't even get close to beating Felix so owners of supercomputers here's your

Chance to implement the first deep blue monkey who can beat Felix should be a piece of cake and now the three by three by three well in this case Felix should be very safe for centuries

To come just like in the case of the two by two by two we'd expect the average number of twists for our monkey to be greater than the number of configurations and 43 quintillion twists at 78,000 twists per second comes to

About 17 million years of fun random cubing okay so finally to ensure that this video receives the official seal of mathematics video nests let me show you a proof sketch that the average number of twists from soft is solved for cube

Is exactly this number of configurations that's the really really cute result in this video right so the main ingredient of this proof is that every configuration of the cube is substantially identical that may seem

Crazy since the whole point of cubing is to get the cube into the one and only solved configuration here's what I mean by substantially identical if you take a solved cube and a scrambled cube and you remove all the color stickers the

Underlying blank cubes are indistinguishable so structurally there are absolutely no differences between the different configurations of the rubik's cube okay for our proof we hand our monkey a solved cube and then evil

People that we are we make the poor monkey twist the cube for all eternity we then record all the step counts at which the monkey holds a solved cube in his hands so since we started solved there is a mark at zero now the monkey

Makes one twist then the cubes definitely not it solved and so there is no dot across from one at this point there's a real chance that the second twist will just be the first twist in Reverse which would bring us back to

Solved after only two twists making for one happy monkey let's say that this has happened in our particular experiment and so we would put a dot next to two anyway let's use orange dots to make two instances where the cube has returned to

Solved now to find an approximation of the average recurrence time we just make n twists where n is some super huge number and then divide n by the number of dots up to this point now pushing n to

Infinity this approximation will converge to the true average all right now all this tells us what we mean by the average but of course it doesn't indicate what the average actually is to get an idea of that let's extend our

Diagram to the right like this so at the bottom we now list all possible configurations and with all the dots in place indicating when the monkey visits these configurations this is a complete record of the monkeys stumbling through

The different configurations also notice that after n twists the diagram will contain exactly n dots one for each twist there are now three easy steps to figure out our average first unless he's the

Unluckiest immortal monkey ever our monkey will eventually visit every single configuration it's like waiting for the 6in Ludo to appear it make take like a zillion years and sometimes in Luda it feels like that but eventually

It will happen second since none of the configurations of the cube is structurally distinguished in any way after a very large number n of twists we can get a good approximation of the average Riya interested in by using the

Dots in any of the columns not just the first 1/3 since after n twists that exactly n dots in the diagram the number of dots in each column is approximately this total number n divided by the number of configurations and of course

This simplifies like this again as you push the number n to infinity this approximation will turn into the Equality we were shooting for and except for a few fiddly details we've left out that's the proof the average number of

Twists it takes for the monkey to go from solve to solve is exactly the number of different configurations the same proof applies to many other random acts those whose different states are

Indistinguishable as an easy example rolling a standard six-sided die there are six indistinguishable states and so our argument also implies that on average it takes six rolls of the die to get a six

Similarly if instead of twisting a Rubik's Cube we simply have the monkey jump randomly from scramble to scramble sort of like rolling a 43 quintillion sided die then the average number of rolls between soft

Configurations showing up is again 43 quintillion exactly the same number as when the monkey moves by normal twisting not so intuitive isn't it but not how to understand if you puzzle through the proof it's also worth mentioning that

There are actually two different ways to count the twists when scrambling cubes most people would count one twist for either rotation of 90 degrees 180 degrees or 270 degrees which equals 90 degrees in Reverse this way of counting

Is called the half turn metric and all the numbers in this video so far relate to this way of counting the second way of counting only allows quarter turns which I personally and many other mathematicians prefer here clockwise and

Counter clockwise quarter turns still count as one twist as before but half turns count as two the second way of counting is called the quarter turn metric there half turn metric and quarter turn metric so when people say

That God's number is 20 they actually mean that God is using the half turn metric on the other hand for a rival God using the quarter turn metric her number will be 26 and this was only proved in 2014

Notice for completeness sake God's numbers for the two by two by two are 11 for the half turn metric and 14 for the quarter turn metric what about our average numbers do our average numbers also change when we change from half

Turn to quarter turn well the average from scramble to solve for the tuba tuba – does change from roughly 4.5 million in the after metric to 4.6 million in the quarter-turn metric however and this is again really

Nice the average number from solved to solved stays unchanged which is also pretty clear from the proof what about the 3 times 3 times 3 with respect to a quarter-turn metric well again soft to solve is our usual 43 quintillion

What about scramble dissolved well as was beating Felix brute force computer simulations are completely out of the question here on the other hand I'd expect the numbers for scramble to solved to be larger and that for solved

To solve was in terms of the half turn and the quarter turn metric but maybe again not that much larger so maybe also somewhere in the quintillions okay here then is my challenge to all the real experts find the exact average numbers

Of scrambled resolved I certainly think that the one for the two by two by two should be doable wouldn't it be great if a youtube video like this one here actually inspired someone to do some serious research in rubik's cube

Mathematics for the non-experts here's a more modest challenge figure out the average number scrambled to solve of the 1 x 1 x 1 cube here I consider the 1 x 1 x 1 cube solved if it is in this particular fixed position in

Space and the monkey scrambles by giving it quarter turns around three phase X's right so finally I should mention that there is a lot more really beautiful mathematics to be discovered in terms of mean recurrence time even in situations

That are not as symmetric is our twisty puzzles the excellent PBS matt's general infinite series did a very nice video on the classic problem in this respect the problem of finding the expected number of random jumps it will take a night to

Stumble from some corner of a chess board back to the same corner definitely also check out the video and afterwards join me and a lot of other people and write to PBS asking them to reverse the terrible decision to

Cancel the wonderful infinite series channel and that's it for today happy cubing you