This blog is highly personal, makes no attempt at being politically correct, will occasionaly offend your sensibility, and certainly does not represent the opinions of the people I work with or for.
The Rubik's cube and the usually wrong human native understanding of complexity
avatar

Below is a verbatim (minus the introduction) email that I sent to a friend this morning, after that she insisted in taking my cube to her place as to mix in a way (meaning spending hours doing it) that it would be impossible for me to solve it.


So let us start at the beginning. First, I will call "center" of the cube, the cube in its solved state.

The cube has got a very *very* large number of configurations (exact number can be found on the wikipedia page). And for some people (and this might have been the case for you at the beginning), the more you "mix" the cube, the more you move farther away from the center, and consequently the more difficult it is for me to solve it. Unfortunately this was the incorrect way of seeing it.

The correct way of seeing it is as follow: imagine a ball (size doesn't matter). Each configuration of the cube is a point within this ball. There are lots of configurations, but this is fine since there is also an infinite number of different points within the ball. When you mix the cube and I look at it, I can see the point where I am, but I do not know where the center of the ball is, in other words I do not know that to do to move directly to the center.

What I do, though, is looking for the nearest "refuge", like snow mountain refuges. I may not know where the center of the ball is, but there are lots of refuges spread within the ball and I can see where the nearest is. The nearest is actually always very near your current position (and maybe the starting position was a refuge itself). Once I get there, I know that I am in a refuge, but I still don't know where this refuge is within the ball and where the center is (relatively to this refuge). This said, refuges have got an interesting property: they always have a map showing the position of another nearby refuge which is guaranteed to be closer to the center. So I go out of the refuge and walk towards the other refuge. Once there, I look at the map and have directions to yet another refuge.

So, in fact, I move from refuges to refuges and I know that each jump brings me closer to the center. The center is actually the last refuge of the journey. So in the end I move from my initial position to the center without ever knowing where the center actually was. The most crucial move is the jump from the very initial position to the nearest refuge, but as I said it's actually the easiest.

Cheers,

ps: Imagine that an entity (maybe an artificial intelligence) can see all the cube at once. Every time you give them a cube they do not jump from refuges to refuges but move directly to the center. The question is how many steps do they need in the worst case ? In fact this question is reformulated as: what actually is the radius of the ball. The answer to this question has been an open question of combinatorics (a part of mathematics) for a while, but now we have the answer. The radius is 20.

So, in theory, no more than 20 moves are needed to move from any position to the center of the cube. My method takes 80 moves in average, that I now do in two and half minutes.

[ add a comment ]

Archives