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 🙂

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.

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.

lmaoo 10:10 "the god of speedcubing"

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…

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.

Mathologer please see xkcd.com/356

If people are hurt I put this on you!

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

Okay but what about the Devil's algorithm

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

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.

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.

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

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???

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

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.

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

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.

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

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

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

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.

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

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

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.

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

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?

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.

Lol I’m the only cuber here

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

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.

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.

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.

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

feliks' 4.22 is the world record

Romanain flag on his t-shirt

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

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?

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

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.

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.

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

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

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.

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.

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.

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

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?

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?

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.

im a cuber and this made me cringe

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.

Anyone else a cuber?

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

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

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

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.

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?

i like it

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

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

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.

Sir please make video how to solve 8 power eq.

I didn't get the proof😅

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.

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

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

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.

you are an awesome nerd

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

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.

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!

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?

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

okayway 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 cubeora superflip (only works for odd-numbered cubes), which greatly reduces the complexity of the affair for configurations with a c over 10)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…

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

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.

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

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

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

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

Is this the kind of thing ergodic theory talks about?

On average, it would take a human 70 years to die

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

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?

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

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.

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.

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

FIS DE CHIENNEFIS DE CHIENNE

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!

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

For a 1×1 cube it is O(1)

Was Mr. Polster ever a Pollster?

You mean Monkologer?

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….

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

why is this so true

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

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

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

@7:45 At this point I'm really interested in why my intuition is wrong. Intuitively, it

feelslike 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.

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?