3
$\begingroup$

It's now known that to reach the solved position of the rubik cube from any other position you need at most $20$ moves (a $180^{\circ}$ of a face is counted as one move , not two ) .

See for example here : http://www.cube20.org/

Now I'll define $d(A,B)$ be the distance between the two positions of the cube $A$ and $B$.That is the minimal number of moves to reach $B$ from $A$ .

Let's denote with $P$ the set of all the possible positions and with $\phi$ the solved position .

From the above :

$$\max_{A \in P} d(A,\phi)=20$$

Now my question is :

What is $$\max_{A,B \in P} d(A,B)$$ That is : How far two positions can be from each other ?

What I have :

It's obvious that $d(A,B) \leq d(A,\phi)+d(B,\phi)$ (triangle inequality :))

So $$d(A,B) \leq 20+20=40$$ but I kind of doubt that $40$ is the maximum .

My intuition is that it's in the $20$-$30$ range .

What do you think?

Thanks in advance for all the help !

$\endgroup$
  • 2
    $\begingroup$ What is so special in the ''solved'' position? It seems to me that any position can be assumed as a solution so the maximum distance from any two positions is $20$. I'm wrong? $\endgroup$ – Emilio Novati Oct 16 '15 at 14:42
2
$\begingroup$

Let $G$ the Rubik's cube group of legal moves of the Rubik's cube under concatenation. Then there is a one-to-one correspondence between the set $P$ of legal positions of the Rubik's cube, and the group $G$, by associating to every position $X\in P$ a concatenation of moves $\varphi(X)\in G$ leading from the starting position to $X$. This immediately yields a distance function $d'$ on $G$ defined by $$d'(g,h):=d(\varphi^{-1}(g),\varphi^{-1}(h)),$$ for all $g,h\in G$. Now it is clear that for all $g_1,g_2,h\in G$ we have $$d'(g_1,g_2)=d'(g_1h,g_2h),$$ because a series of moves leading from $\varphi^{-1}(g_1)$ to $\varphi^{-1}(g_2)$ also leads from $\varphi^{-1}(g_1h)$ to $\varphi^{-1}(g_2h)$, and vice versa, as such series of moves represent $(g_2h)(g_1h)^{-1}=g_2g_1^{-1}\in G$. Hence for all $A,B\in P$ we have \begin{eqnarray*} d(A,B)&=&d'(\varphi(A),\varphi(B))=d'(\varphi(A)\varphi(B)^{-1},\varphi(B)\varphi(B)^{-1})\\ &=&d'(\varphi(A)\varphi(B)^{-1},\varphi(\operatorname{id}_G))=d(AB^{-1},\phi), \end{eqnarray*} which shows that $d(A,B)\leq20$ holds for all $A,B\in P$.


On a more conceptual note; considering the 'shifted' distance function $$d''(A_1,A_2):=d'(\varphi(A_1)\varphi(B)^{-1},\varphi(A_2)\varphi(B)^{-1}),$$ which I implicitly use in the last part of my answer, comes down to considering $B$ as the 'solved state' of the Rubik's cube in stead of $\phi$. The rest f the argument then says that a series of moves leads from $A$ to $B$ if and only if it leads from "$AB^{-1}$" to $\phi$. This is also the basic idea of the other answer by Mike Haskel.

$\endgroup$
7
$\begingroup$

By symmetry, no two positions can be more than 20 steps apart. There's nothing special about the "solved" configuration: the same argument that shows you can get from any starting $A$ to the solved state in no more than 20 steps shows that you can get from any starting $A$ to any fixed $B$ in no more than 20 steps.

$\endgroup$
  • $\begingroup$ I like your answer. Simple, and straight to the point! No rigor needed. $\endgroup$ – Christopher Mowla Oct 17 '15 at 12:52

Your Answer

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