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 :)
What's the intuition for the Mean Time from Equilibrium being greater than the Mean Recurrence Time? Is it because the mean recurrence includes all the cases where the cube doesn't get very scrambled?
For the 1x1x1 mean time from equilibrium in the 1/4-turn metric, I find 99/4=24.75, using that each of the 24 starting orientations are equally likely.
Edit:
Extending method to 1/2-turn metric gives 973/40=24.325. The order 24<24.325<24.75 is reassuring.Edit2: Missed something, and 1/2-turn metric actually gives 189/8=23.625.
/u/ThisUserEatingBEANS does this video answer your question (/r/math/8jzxl6/) from a few weeks ago?
On a not Math related note: am I the only one who reads Mathologer's name as "Mathloger"?