Welcome to another Mathologer video. Today's video should be of interest to
everybody who loves twisty puzzles as well as all hardcore Mathologer fans. In
2010, thirty 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
closely 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 enough 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 Mathologer 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 2x2x2
cube. I've been assisted by my new best friend computer wiz Erich Tomanek 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 maths 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, which 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 there 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 stochastic 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 of 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 3x3x3 for the 2x2x2
and for many other twisty puzzles. So, for example, in the case of the 2x2x2
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 solved to solved and for the 3x3x3 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 Erich enters the picture. Among other things Eric 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. Erich 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 Erich and I
tried was to test a theoretical result that I just mentioned. So for the
2x2x2 we had a virtual slave monkey stumble from solved 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 the average 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 cubers. It
has been solved with an ingenious Gordian knot approach. The World Cubing
Association (WCA) which provides the scrambles for cubing competitions actually doesn't
use random twisting at all to create their 2x2x2 and 3x3x3
scrambles. They used to execute 25 so-called non-redundant random twists
for both the 2x2x2 and the 3x3x3 to randomize but they don't do this
any longer. What they do these days is to use a
computer program called tnoodle 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. Okay 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 exploding and
reassembling cubes until a solvable configuration results. Neat isn't it?
Actually I had a great discussion with Jeremy Fleischmann and Lucas Garron, two
of the speed cubers behind tnoodle and discovered that there's a whole video
worth of material about how they make sure that the different kinds of twisty
puzzles 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 we scrambled using
exploding and 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 are 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 and so to
give us humans a fighting chance let's give the computer a bit of a handicap,
let it solve a la monkey. Okay, so the God of speed cubing is Feliks Zemdegs who
just like me happens to live in Melbourne in Australia. His best
2x2x2 time is 0.79, believe it or not, seconds and his best
3x3x3 time is 4.22 seconds. I know
completely insane, right? :) So how would Feliks fare against one of
Erich's monkeys on his best day. Okay, first the 2x2x2. Well Erich's monkey
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 Feliks. So owners of supercomputers here's your
chance to implement the first Deep Blue monkey who can beat Feliks, should be a
piece of cake. And now the 3x3x3. Well
in this case Feliks should be very save for centuries to come. Just like in the
case of the 2x2x2 I 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 videoness. Let me show you a proof sketch that the average number
of twists from solved to solved for a 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 at solved
there's a mark at zero. Now the monkey makes one twist. Then the cube is
definitely not at solved and so there is no dot across from 1 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 2. Anyway
let's use orange dots to mark all instances where the cube has returned
to solved. 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. Alright 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 visit 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 6 in Ludo to appear it may
take like a zillion years and sometimes in Ludo 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 we are interested in by using the
dots in any of the columns not just the first. Third, since after N twists there are
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 solved to solved is exactly the
number of different configurations. The same proof applies to many other random experiments,
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 6 rolls of the die to
get a 6. 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 the the solved configuration 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 hard 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 a 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. This 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. Now just for completeness sake God's numbers for the 2x2x2 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 scrambled to solved
for the 2x2x2 does change from roughly 4.5 million in the half turn 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 3x3x3 with respect to the
quarter-turn metric. Well again solved to solved is our usual 43 quintillion.
What about scramble to solved? Well as with beating Feliks, brute force computer
simulations are completely of the question here. On the other hand, I'd expect the
numbers from scrambled to solved to be larger than that from solved to solved both
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
to solved I certainly think that the one for the 2x2x2 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 solved 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 the 3 face axes. 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 maths channel 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 knight to stumble from some corner of a chess
board back to the same corner. Definitely also check out this
video and afterwards join me and a lot of other people and write to PBS asking
them to reverse their terrible decision to cancel the wonderful Infinite Series
channel. And that's it for today. Happy cubing :)