2
$\begingroup$

I'm trying to write a project about the Rubik's Cube, and althought it's easy to find out the lower bound (using half turns) is 18, finding a precise proof hereof seems impossible.

How does one proof that god's number must be greater than or equal to 18?

$\endgroup$
4
$\begingroup$

I'm sure you've seen it already but just in case you haven't, check out the wikipedia section on lower bound. https://en.wikipedia.org/wiki/Optimal_solutions_for_Rubik%27s_Cube#Lower_bounds

ruwix.com also has a nice graph of the historical progress of calculating God's Number: enter image description here

I'll first explain how we get a lower bound of 16, working our way up to 18.

We know that there are 43 quintillion unique positions for the Rubik's Cube. That's $4.3\times10^{19}$. Now in half turn metric, there are 18 different moves you can make (three moves for each side). So the maximum number of positions we could possibly reach in 15 moves is $18^{15}\approx6.7\times10^{18}$. (This is way more positions than we can actually reach, however, because a lot of positions are double counted, but that's ok for our analysis.) So that means we can't possibly get all 43 quintillion positions in 15 moves, so we know we need at least 16.

But wait we can do a little better. There are 18 possibilities for the first move, but for every move after that, we don't need to turn the same face any more. So after the first move, we only need to consider 15 possible moves. So applying the same argument we had before, after 16 moves we can only possibly reach $18 * 15^{15}\approx7.8\times10^{18}$ positions. And that is less than the number of all Rubik's Cube positions so now we know we need at least 17 moves.

But wait we can do even better! There are still 18 possibilities for the first move, 15 possibilities for the second move, but if the second move was on the opposite face of the first move, we no longer need to count moves to the first OR second face any more, because moving opposite faces don't affect each other. So in this case, there would only be 12 possibilities for the third move. Unfortunately coming up with a nice formula for this is tricky (we'd have to do careful casework for when two consecutive moves are on opposite faces). The point is, instead of saying every move from the second move on has 15 possibilities, some of them now only have 12. And with careful counting, we can see that 17 moves is not enough to get all Rubik's Cube positions. It turns out that on average, there are 13.35 possible moves after the first move. So that gives us $18 * 13.35^{16}\approx1.8\times10^{19}$, showing that 17 moves are not enough. And that's how the original lower bound of 18 was reached.

This paper (in the "Problem Space" section, with Table 1) https://www.cs.princeton.edu/courses/archive/fall06/cos402/papers/korfrubik.pdf gives a little more detail, as well as exact numbers.

Eventually, it was theorized and confirmed that the superflip takes 20 moves to solve. That was in 1995. Finally in 2010, the upper bound was confirmed to be 20 moves. That means that the superflip is an example of a position that is "farthest away" from being solved.

$\endgroup$
  • $\begingroup$ Thank you for the detailed explanation, as a follow up question, I've noticed you using 18*15^(n-1) for the lower bound, using the position function (ill just call it that for this purpose) only for n moves, whereas other authors such as Singmaster use the sum of all functions from 0 to n ( 1+18+18*15+18*15^2+...+18*15^(n-1)) to get all positions reachable in n moves and then set that equal to 4.3*10^19 to get their lower bound. Which is correct? or more correct? $\endgroup$ – Mychil Oct 24 '18 at 9:17
  • 1
    $\begingroup$ Call $P$ the number of cube positions, 43 quintillion. So the idea is let's call $X$ the number of positions we can get to in $n$ moves. And if $X$ is less than $P$, then we know we need at least $n+1$ moves to solve any cube. With increasingly sophisticated arguments, we can reduce $X$ for a given $n$. That means for larger $n$, we can make $X$ to still be less than $P$. That is how our lower bound started at 16 and worked its way up to 18. So which one is more correct? Well... technically adding a +1 to the calculation is more correct, but it doesn't matter, as it's still way less than $P$. $\endgroup$ – timidpueo Oct 24 '18 at 16:12
0
$\begingroup$

Use the pigeon hole principle

In 17 moves there are less distinct sequences of moves than there are distinct starting cube positions. They're both on the order of 10^19 but the number of cube positions is greater.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.