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

By | February 14, 2020


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 🙂

100 thoughts on “What’s the Monkey number of the Rubik’s cube?

  1. Roice Nelson Post author

    I'm curious if you and Erich explored the shape of the distribution for the recurrence time (rather than just the mean)? I suspect it is fat-tailed vs. a normal distribution because of scenarios like the 2-move solve you pointed out. Understanding this distribution might be helpful with the "mean time from equilibrium" question.

    Reply
  2. Jake Malloy Post author

    I've been thinking about the pocket cube recently. If one restricts to turning only one axis, then the options can be represented one-dimensionally. Of course, it is a circular geometry (or 1D spherical). If we use two axes, then the geometry of configurations seems almost 2D spherical, but in this case it is noncommutative. I'm beyond my depth at that point, but I would love to learn more.

    Reply
  3. Penny Lane Post author

    Has anyone ever tried giving a computer monkey author a computer editor in the form of autocorrect?

    I mean, you wouldn't reject a human author's manuscript just because of a few typos…

    Reply
  4. Stefan Buller Post author

    I'm so glad you included the bit at the end about the quarter turn metric. Having a single antipode is so much more satisfying. Also, I'm glad I watched to the end before I commented.

    Reply
  5. Ikantspell4 Post author

    Mathologer please see xkcd.com/356
    If people are hurt I put this on you!

    Reply
  6. its yoda Post author

    Did anyone else notice that at 3:25 when the twenty is hilighted, the cube that represents it is in a super flip configuration?

    Reply
  7. Robert Tumlinson Post author

    Okay but what about the Devil's algorithm

    Reply
  8. Joseph Price Post author

    Can someone tell me book collection I am thinking of but can’t remember that his shirt is referencing.

    Reply
  9. Donald Kronos Post author

    Some of the monkeys watching this video might be insulted by your portrayal of monkeys as incapable of learning to solve a Rubik's Cube any more efficiently than random chance. Especially if you use a monophyletic phylogenetic definition of "monkey", which would include humans.

    Reply
  10. kurtu5 Post author

    The gesticulation frequency that PBS Digital Studios have in their productions has bothered me to the point where I can't stomach watching them. Its like watching a bobble head, when you are expecting a person. Its uncanny and unsettling.

    Reply
  11. SuperDomKiki Post author

    Still wondering how 16 people clicked on that video and got disappointed, I must be missing something there.

    Reply
  12. realflow100 Post author

    I get it so. every combination if you were to randomly scramble the cube for as many combinations as there are. to the power of as many combinations as there are. there would be an equal number of chances for it to be any given combination including solved and completely scrambled.
    Something like that???

    Reply
  13. Enrico Lucarelli Post author

    Very interesting and amusing, as allways👍. Question: what is the number scrambled configurations that actually require at least 20 movements? It seems to me that a fair competition scrambler should make sure that the starting configuration is one of these combinations

    Reply
  14. andymcl92 Post author

    It might seem counter-intuitive that solved to solved takes fewer moves on average than scrambled to solved. You might think "But it has to go through scrambled first so why isn't solved to solved twice as long?" The solution was hinted at in the video, but maybe a more blatant explanation is needed. Solved to solved includes the possibilities where you simply do one or two moves and then reverse them, so solutions that are much less than the average. It also includes many that are much larger, where you maybe come withing one of solving the cube, and then stray away from the solved state for a while. This is what brings the average to the total number of possible states. However, when you are going from "well scrambled" to solved, you are not allowing the starting configurations that would only take one or two moves to solve the cube, but maybe only ones that take at least 5 moves, making it much less likely to get a short solve. This means the larger numbers still occur but the smaller ones do not, so the average gets driven up.

    Reply
  15. nickt Post author

    how can solved to scrambled be different from scrambled to solved? the moves can be reversed, or simply swap the sticker configuration

    Reply
  16. Fester Blats Post author

    Does anyone know how many turns a top cuber uses to solve a 3x3x3 on average? It would be fun to see how efficient they are compared to the maximum 20 turns needed.

    Reply
  17. warumbraucheichfüryoutubekommentareeinescheissgooglepluspagefragezeichen Post author

    There is a similar idea with monkeys instead of letters. In a finite amount of time (which can also be veeeery long, but much shorter than an infinite amount of time) you could try out all possible colour combinations of an image of a defined size like 1920×1080 with a defined colour depth like 24 Bits. The result would be ANY image you could possible imagine. That idea is quite mind blowing. There is a blog post about that idea: http://www.mathegedanken.de/bitmap-zeigt-alle-bilder

    Reply
  18. BlackCubing Post author

    I think the mean time from equilibrium for the 1×1 cube is 42 moves

    Reply
  19. Knighty02 Post author

    I always get chills when someone says my first name in a Youtube video

    Reply
  20. Colopty Post author

    I remember bringing the scrambled to solved problem up about a year ago. The people I asked kept insisting the answer was 20, because that's what google told them.

    Reply
  21. Richard Short Post author

    Is it bad that this makes me think of Dr. Scratchensniff from Animaniacs?

    Don't know what to say the monkeys won't do.

    Reply
  22. Alcesmire Post author

    78000 twists seems awfully slow to me if it's just random moves. Any reason for this?

    Even in a rather slow programming language (say python) you can get up to the order of 100k to a million random numbers in a second, and for faster implementations you can get a lot more than that (e.g. 10 million in half a second with pypy). So unless there is some huge cost of permuting the cube and checking for correctness the 78k figure seems weird.

    Reply
  23. The YouCubers Post author

    Finally found someone that understand the cube and know there's WCA

    Reply
  24. Zachary Kaplan Post author

    So I know how to do the problem given at the end of the video, but it involves me making a 24 by 24 matrix, with each row and column corresponding to one of the states, with 0's everywhere unless you can transition from the row state to the column state, in which case you put an entry of 1, with the states in the same order for the rows and columns. Then, you divide each row by its sum, to change it into the probability matrix, which you then modify by setting each entry in the row and column of the solved position to 0, and call this matrix A. Then if a vector x has the probability of the matrix being at a certain state (each entry corresponding to the column), Ax has the probability of all of the twisting you can do to the matrix.
    This is a symmetric matrix, and since it has this "probability minus a little bit" feel, we hope that as n goes to infinity, A^n*x goes to 0. Note that what we care about for average solve time is slightly different- the percentage of cubes that achieve the solved state at step i+1 is it is |x_i|-|Ax_i|=|x_i|-|x_(i+1)|=f(i+1), so really what we want is the sum from i=1 to infinity of i*f(i)

    So, if there is some nice, closed form version of f(i), you can probably plug it into wolfram alpha. And thankfully for us, there is, because as already mentioned, A is real and symmetric, and as such has an eigenvalue decomposition and can be written as VDV', where D is a diagonal matrix and V is orthogonal.Then, f(i+1)=|x_i|-|VDV'x_i|=|VD^iV'x_0|-|VD^(i+1)V'x_0|, where we set x_0 to be the matrix with 1/24 at every position, i.e. an equal chance to be at every ruby position state, and you're done!

    … except that I don't know how to simplify down f(i).

    Lets try a different strategy: this time, we're going to change the matrix A so that the entry corresponding to the row and column of the solved position is 1. , i.e. once you are at the solved position, you stay there. Then, set f(i+1)=x_i+1,(solved position)-x_i,(solved position)=x_(i+1)*e_s-x_(i)*e_s=e_s*(x_(i+1)-x_i), where e_s is the standard basis column vector corresponding to the solved position, and * is inner product. Notice that the "direction of the subtraction" reversed. Then, we still want the sum from i=1 to infinity of i*f(i). We still need a closed form for f(i+1), and the approach starts off the same way, but is much more successful- f(i+1)=e_s*(x_(i+1)-x_i)=e_s'(VD^(i+1)V'x_0-VD^iV'x_0)=e_s'V(D-I)D^iV'x_0. Grouping usefully, this becomes: f(i+1)=(e_s'V(D-I)) D^i (V'x_0), using the same x_0 as before.

    f(i) then is not geometric, but its close- For some constants a_m, it can be written as a_1D_1^i+a_2D_2^i+…a_24D_24^i, which is definitely good enough to get a number for the sum from one to infinity of i*f(i), by separating each of the terms and summing them up separately.

    There are 2 flaws in this approach: The eigenvalue decomposition is not guaranteed (and in fact, probably wont) only contain say algebraic numbers in it, particularly if done iteratively (like every computer ever does it), but this would just need to be checked for this example, and the other flaw is I reallyyyy don't want to make the matrix

    Either way you cut it, this does not seem to be the correct way of doing this calculation. Anyone have any comments on this or better ways to do it?

    Reply
  25. Jack Kenny Post author

    Not sure about the proof from solved to solved. Doesn't seem like it factors in the 1/12 chance to solve the cube in 2 turns.
    It seems like the proof you gave is the proof from 1 specific configuration to any other specific configuration chosen at random from all possible configurations.
    The answer for solved to solved should be slightly lower then that and the answer from perfectly scrambled to solved should be slightly higher.

    Reply
  26. Chenxing Li Post author

    Fellow audience, we should write to PBS, tell them that it's a horrible decision to shut down Infinite Series, and demand that they bring the show back! https://help.pbs.org/support/tickets/new

    Reply
  27. Karsten Meinders Post author

    I prefer counting quarter-turns but I guess a half-turn can be done as quick as a quarter turn so execution time must be differentiated from counting cycles.

    Reply
  28. Ben C Post author

    You mentioned that the recurrence time is the same whether you use the 1/4-turn or 1/2-turn metric.

    So what if we use a 26-quarter-turn metric? In this metric, one "turn" is any combination of 26 quarter-turns.

    Since God's Number is 26 (in the 1/4-turn metric), we can always solve the cube with just one of these big "turn"s. We just have to pick the right one.

    Thinking about recurrence time, the diagram you drew looks the same, so the reasoning should work the same. I can still do one "turn" and end up somewhere (e.g. superflip 🙂 and then get lucky and get back from there with one "turn", since any state of the cube is within 26 1/4-turns of any other.

    So I think the recurrence time is the same in the 26-quarter-turn metric as in the 1/4-turn metric.

    But the number of turns needed to scramble the cube is surely just 1 in this 26-qt metric. It's just like rolling a die– you only have to roll it once to "scramble" it. In the 26-qt metric our cube essentially becomes a 43 quintillion-sided die.

    So to answer the question: how many moves is enough to scramble a cube in the regular 1/4-turn metric? Well 26 random 1/4-turns is equivalent to a single random turn in 26-qt, so I reckon 26 1/4-turns (or 20 1/2-turns) should be enough to scramble the cube.

    Reply
  29. David Giles Post author

    Agree, we shouldn’t have to wait for monkeys or anyone to scramble/unscramble possible combinations of particles in any multiverse to continue to enjoy “PBS Infinite Series“. Not a forward-thinking decision on the part of PBS to cancel it. The hosts, all 3, were gifted presenters of fascinating, thought-provoking material normally obtuse for almost anyone without a higher mathematics background. The kind of show (like yours) that can inspire folks to pursue math and science careers as they realize mathematics is a rosetta-stone for deciphering creative processes at work in nature, and which also reveals ways for them to create the kind of better future we all hope to live in.

    Enjoyed this video. Look forward to other Boltzmann (via monkeys if you want) related topics you might choose to do. In an era where content decisions can correlate with lowest common denominator trends, glad you are continuing to make videos.

    Reply
  30. Russell Schwartz Post author

    Great video! I loved the way you walked through your explorations.

    Reply
  31. Dr. Francis B. Gröss Post author

    Question No 3: Why use a monkey at all when having a solved Rubik's cube?

    Reply
  32. John Doe Post author

    If I used the proof method to get the scrambled->solved number as well, wouldnt i end up also getting # of configurations as my answer? What am i missing?

    Reply
  33. Jorge C. M. Post author

    How come God's number exists but God doesn't exist?

    Reply
  34. musaed alsubaie Post author

    I find your jokes about almighty God in poor taste and I’m sure some of your viewers are offended by them. I come to your channel because it`s entertaining and informative, but if you use it to propagate your religious views (yes atheism is a religion) then I will have to do without it.

    Reply
  35. ljfa Post author

    I once held a seminar lecture about random walks on an integer lattice, and one of the results was that the expected recurrence time was infinite (for the symmetric case). Makes sense, since in this case the number of possible states is infiinite.

    Reply
  36. Jolly Colb Post author

    Every time I scrarnble I always think it is not scrambled enough 𝘌𝘷𝘦𝘳𝘺 𝘛𝘪𝘮𝘦

    Reply
  37. Michał Kuczynski Post author

    Your videos are fantastic and I'm looking forward for more 😀

    Reply
  38. Park Tamaroon Post author

    The discussion on half-turn and quarter-turn metrics didn’t mention if turning a middle layer counts as a single step. I’m guessing it counts as one step, despite the prevailing move notations representing a center turn as two turns of the flanking layers.

    Reply
  39. David Stolp Post author

    Average twists to solve (half-turn metric): 4410504.275
    Average twists to solve (quarter-turn metric): 4647940.184

    Let X be a random variable representing how many twists it takes the monkey to get from a solved state back to a solved state. The answer we seek is (E(X^2)/E(X)-1)/2. E means expected value. As noted in the video, picking a random configuration is equivalent to picking a random time in the monkey's history, thus asking how long it takes to solve a random start state is equivalent to asking when the next solved state is after a random point in time.

    To compute E(X^2), I used a computer simulation. Initially there were way too many states. The state graph has many symmetries, so many states can be combined together. Doing this resulted in a graph with just 77802 states. I simulated the first 2000 twists. After 2000 twists, the probability density function of X is indistinguishable from a geometric distribution, so I used that as an optimization to get the final result.

    Reply
  40. Park Tamaroon Post author

    I once bought the entire finite number of 0-cube twisty puzzles that were in stock at Toys Я Us. They were on sale for 25% off so I paid zero dollars each plus 5% sales tax. I saved the null receipt made of no thermal paper so I could deduct the purchase from my tax. As it turns out my profession is very very secret Santa and I pay income tax to the North Polar Coordinate Revenue Service on the payments I don’t collect from my free gifts. I put a handful of these in everyone’s stocking that year. Turns out they all have a monkey number of 1, even if unique rotations are counted separately. I got my monkey at the animal shelter for degenerate simians and null beasts. He bites sometimes.

    Reply
  41. Grzegorz Pacewicz Post author

    In speedcubing we say "turns" for what you mean "twist". "Twist" means phisicall corner rotation whitout turning the cube.

    Reply
  42. A haunted account Post author

    I think I'm missing something: The sketch of the proof tells us that we can consider any starting configuration of a cube, and the expectation will be the same: the number of permutations. But isn't that exactly what we're asking the monkey to do in problem 2?

    Reply
  43. Joseph Noonan Post author

    Is it just a coincidence that, for both metrics, God's number for the 2x2x2 is just God's number for the 3x3x3 divided by two, plus one?

    Reply
  44. Joseph Noonan Post author

    I had a feeling when the average number of turns was equal to the number of configurations that the proof would involve the fact that all configurations are functionality the same.

    Reply
  45. willprogresivo Post author

    Wait, what? So for any of possible states a Rubik's cube can be in, and that every cuber perform several algorithms on to solve, you could actually solve it in less than 20 moves? That doesn't sound right… EDIT: I just googled about this. Well, they count a 180° turn as a single turn, and I consider that to be two turns. So god's number is a little bigger.

    Reply
  46. Austin Molitor Post author

    For your math did you use quarter turn metric, half turn metric, or slice turn metric? It would have an effect on the results.

    Reply
  47. Albert Chow Post author

    When the computer "explodes"and rearranges all of the pieces, wouldn't it be possible for it to make a parity error?

    Reply
  48. Karl Young Post author

    Here’s an example of bad reasoning but I’m not sure why (I should probably wait until the end of the video and whatever proofs you go through; I stopped when I first got confused). It seems counterintuitive to me that the mean time from equilibrium should be so much larger than the mean recurrence time. Maybe I’m being led astray by the mean recurrence time being equal to the number of configurations. That seems to suggest to me that some significant fraction of the configurations occur during a given “recurrence trial”, ergo there’s a reasonable likelihood

    Reply
  49. Ben C Post author

    If you're scrambling a pocket cube, (or a 4x4x4 but a 3x3x3 is OK), you can't just say "Do N random moves". You have to start by flipping a coin to decide whether you're going to do N or N+1.

    Reply
  50. Aron Moberg Post author

    You say that the number of moves to get from solved to solved is the same for both the half turn metric and the quarter turn metric. Is this really true? For the quarter turn metric there are 12 possible moves: U, R, L, B, F, D, and the inverses (18 if middle layer moves are allowed). This gives the monkey a 1/12 chance to get back to the solved state in just two moves. If half turns are allowed the number of possible moves doubles and thus the chance of getting back to a solved state in just two moves is halved compared to the quarter turn metric. This should affect the average right? Is this equaled out by the fact that the half turn metric can get back to a solved state in 3 turns whereas the quarter turn metric can not?

    Reply
  51. Ilea Cristian Post author

    Is there an online petition or some "official" place to write to PBS?

    Reply
  52. Dipu Chauhan Post author

    Can you make a video on Ramanuj Sato Series.???

    Reply
  53. Deutschebahn Post author

    I'm glad someone has publicly come out and said that decision to end Infinite Series was shit. It really was. It was one of the best maths youtube channels around. and I don't buy into the change of hosts being innately bad. I actually loved all 3 of them. People just don't like change.

    Reply
  54. Preetpal Singh Post author

    Sir please make video how to solve 8 power eq.

    Reply
  55. SgtSupaman Post author

    It's been tested and we know that no amount of immortal monkeys will ever recreate Shakespeare. The test result with just a single monkey was several pages of a single letter and a broken keyboard (so the mortality of the monkey didn't even matter as it rendered typing impossible). Thus, I believe applying this to a magic cube shows that a monkey will do the same twist over and over before throwing the cube or pulling it apart.

    Reply
  56. Rufino Bartolabac Post author

    Can you do cyclogons? Also cycloids. Let the intro have a square cycloid.

    Reply
  57. Dr. M. H. Post author

    what about a configuration where in each color is maximally broken up by other colors and maximal distance from one another?

    Reply
  58. MathVibes Math Post author

    Hello, I made channel about maths. I will try to post video twice a week or more. There will be puzzles mostly. Please, come and see. Looking forward for all of the feedback.

    Reply
  59. Double Bubble Tube Post author

    is ur Klein bottles still alive? try to put water in them

    Reply
  60. Kevin Thorton Post author

    Hey can you do a video about using math to get out of the inside of a Rubik’s cube? I got sucked into another giant Rubik’s cube again and was thinking about your maths when trying to figure out how I get out.

    Reply
  61. BritneyBitch Post author

    Hey Mathologer, are you possibly having any merch with these shirts? I'd love to buy the: "Math. Nothing 2b^2 of!". It's like my greatest mission yet as a math student. Love your videos!

    Reply
  62. Semi charmed kind of guy Post author

    I feel like I'm missing the obvious here but at 14:17 I don't exactly understand how the diagram can contain N dots. Can somebody explain that?

    Reply
  63. Xavi Arnal Post author

    I feel like a more interesting version of the second problem would be to see how many random moves it takes on average to solve a specific cube configuration. I'm guessing that there's some symmetry in the graph of configurations that makes it so that this number is only dependent on how many moves away that configuration is from a solved cube, which would immediately let you solve problem #2 by computing a weighted average, while also containing a solution to problem #3.

    What's more, I feel like that problem might be easier, or at least easier to approximate. Given a configuration c, let l_c be the minimum amount of moves needed to solve it, and let s(c) be the (random) result of performing a random move on c.

    Evidently, if l_c=0, l_s(c)=1, and l_c=20=>l_s(c)=19
    However, if l l=c=1, there's a 1/12 chance l_s(c)=0, and a 11/12 chance l_s(c)=2. Similarly for l_c=19
    For 2>=l_c<=18, it's definitely not as obvious, but hopefully someone who understands the graph of rubiks cube configurations better than I do can figure out those chances, which turns the problem I mentioned into a remarkably unwieldy but very computable affair . If not, it aso sounds possible to get some approximations of those numbers just by random testings on configurations with a certain l (of course, you'd need an okay way to compute l_c for a certain c – this seems at least doable, since you don't actually need to find a minimal solve for this – just a minimal amount of moves to take you to a solved cube or a superflip (only works for odd-numbered cubes), which greatly reduces the complexity of the affair for configurations with a c over 10)

    Reply
  64. Kram1032 Post author

    So what's the intuition behind it taking longer to solve a scrambled cube than to scramble, then solve? I assume that's due to "lucky" barely scrambled configurations?

    And how long are the necessary mixing times actually? My vague guess is, that something like twice the maximum number to solve (i.e. 40 or 52) would suffice?

    And finally, is there any substantial difference between the metrics?
    Like, if you want to be efficient with respect to one or the other, does the most efficient sequence of moves ever change? – I assume the answer is no, since if quarter turns are ever more efficient, the half-twist metric will just use those. But maybe there are instances where, I don't know, two half-twists (= four quarter twists) can accomplish a solution just as fast as three quarter twists (pretty sure this particular example won't work due to the quarter twists not both being even or both being odd, but something to that effect) which would then mean the most efficient half-twist path is longer (in terms of quarter twists) than the most efficient quarter twist path…

    Reply
  65. DD Post author

    Please do some continued fractions videos, it's something nobody makes videos about 🙂

    Reply
  66. SlimThrull Post author

    You joke that it should be a piece of cake for a supercomputer to do it. However, this kind of thing would be exceptionally easy for an AI to learn. The numbers of moves is far far less than an average Go game. AI's have already surpassed humans in that. With enough runs (thousands? millions?) an AI would be able to solve it nearly instantly.

    Reply
  67. kazi kazi Post author

    Ur vdos r osme.But can you PLEASE make them shorter? You'll get a lot of views

    Reply
  68. Jakub Bronk Post author

    how to you know that rubik's cube has 43 Quintilian combinations? How it was calculated?

    Reply
  69. Ben Goodwin Post author

    I only understand about 2/3 of the math related terms you say, but that’s probably because I’m still taking calculus in high school

    Reply
  70. Blake Winter Post author

    'Our three monkey problems' makes me think of the three body problem, but with monkeys…

    Reply
  71. Arthur Santana Post author

    Is this the kind of thing ergodic theory talks about?

    Reply
  72. rand0m_us3rr :D Post author

    Wie rechnet man eigentlich die ganzen verschiedenen Möglichkeiten aus, wie ein würfel verdreht sein kann? Also wie zum Beispiel beim 2x2x2 die 3,674,160

    Reply
  73. Michael Fik Post author

    Hi I'm trying to find twisty puzzles that are solvable with 3×3 algorithms. EX: mirror cube, ghost cube, and megaminx. Anyone know of any others?

    Reply
  74. TechnoTerror 11 Post author

    Im not sure if you have accounted for this, a wile back I realized that the rubiks technically doesn't just have one solved state, their are actually thousands of them, possibly even tens of thousands of solved states in a regular rubiks cube, it might be a little hard to wrap ones head around it, but you can rotate the the middle prices on a regular rubiks cube, and I suspect if you tell a computer only to look for one of theses solved states it may entirely pass by so perfectly solved positions just because the center pieces weren't oriented currently, is this accounted for in theses calculations? if not you could be massively overstating the average amount of turns it takes to reach one of the thousands of different solved states

    Reply
  75. Karl Deux Post author

    Hi,

    I really like your videos, but here in the case of the 3x3x3 there is something you forgot to consider.

    If you start with a solved 3x3x3 cube, and later got it with only two centers rotated (by a quarter for instance), then the cube is solved though the state is not the one you started with.

    Said otherwise, there is not only one combination for a 3x3x3 cube to get solved, as there is no orientation needed for the center of each color, and this is even more true (truer?) for greater cubes.

    However, what you told is perfectly true if you switch the color of the centers for an oriented pattern (like a sign with no symetry by 180° rotation, the letter A for instance, but not the letter Z). Photographs or pictures generally do the job as well.

    To check my words, get a 3x3x3 Rubik's cube and see how the logo is oriented on the whites, then shuffle it and give it to solve to somebody who doesn't know how it was oriented.
    There is only one chance on four the logo will be oriented the same when the cube is solved again… so now imagine you have a logo on each colors…

    I tried to evaluate by myself, it took me only a few minutes to identify about one hundred (well I stopped at 82) different combinations for which the 3x3x3 cube is solved with only colors. And as I told you this is even "worse" for bigger cubes (because the center part is then also bigger).

    Hope this helps.

    Reply
  76. Bert Blankenstein Post author

    My thoughts on the 3x3x3 God's number:
    Rather than solving every possible configuration, one might make a matrix of every possible configuration, and then track how to get there from a good state. One would start with one twist and then add that to a tree structure. Then add every possible single twist and add those configurations to the tree. One could then track how many steps (from solved) are required to get all the possible configurations. Still requires a super computer however..

    My time to solve the 3x3x3 is about the minutes. I adapted those steps to 2x2x2 but I'm not all familiar with that yet.

    Reply
  77. НАУКА И ТЕХНИКА своими словами - 1 Post author

    ОБ ЭТОМ Я ДОДУМАЛАСЬ17ЛЕТ НАЗАД.И ДЕЛАЛА ГЕНЕРАЦИЮ ИЗ БУКВ.ЖАЛЬ,ЧТО ВЫГЛЯДИТ ТАК,БУДТО ОН ПРИДУМАЛ ЭТУ ЗАДАЧУ,А ДРУГИЕ-ТИПА НЕТ( спасибо за русский перевод!

    Reply
  78. Hans Ignals Post author

    If I peeled off the coloured stickers and rearranged them on to different faces, would the cube be unsolvable? Unless of course it was ‘solved’ by putting it back to the same condition it was in when an attempt was made to solve it!

    Reply
  79. УниКод Post author

    God's number for turns needed to transform one "solved" position to any other?

    Reply
  80. Ulf Post author

    So i dont unterstand why the average from random to solved to should be more than the number of States. Both the random and the solved state are more or less imdistiguishble so the number should also be the number of possible States. The Simulation might have a bug or using non random numbers….

    Reply
  81. Ian Moore Post author

    10:11 "Okay, so the God of speedcubing is Feliks Zemdegs."
    why is this so true

    Reply
  82. Communist Orange Post author

    0:08 lol im a speedcuber and a hardcore mathologer fan.

    Reply
  83. Brian Brinck-Jensen Post author

    with the monkey you are imposing blindness, we know monkeys have some puzzle solving int, but you make them blind and take the worst case

    Reply
  84. What's on my mind Post author

    Coincidentally the number of moveable pieces on the 3×3 is also 20.

    Reply
  85. UbiquitousChe Post author

    @7:45 At this point I'm really interested in why my intuition is wrong. Intuitively, it feels like starting with a solved cube, putting in 100 random twists to randomize it, then randomly solving, should give the answer to Problem 1 less the number of random twists at the start. But the answer to problem 2 is significantly larger than the answer to Problem 1.

    Mathematics is frequently counter-intutiive so that in and of itself is fine. I'm just wondering what the problem in the intuitive reasoning is.

    Reply
  86. Sid Kemp Post author

    Is a quarter turn of the middle rank of the cube considered a single turn, or may one only twist a top-bottom-or-side away from the rest of the cube in a single move?

    Reply

Leave a Reply

Your email address will not be published. Required fields are marked *