Home

Rubix Cube Proof

In this post, we will proof that repeatedly applying any algorithm on a solved Rubixs Cube would cause it to eventually return back to its solved state.

What do I mean by this? Well, supposed your algorithm is to turn the top side once. After repeating this algorithm 4 times, you would return back to the solved state right? In the problem above, “any algorithm” would refer to literally ANY ALGORITHM. For instance, your algorithm might be: R’ D D R D R’ D’ R, and repeating this algorithm a sufficient number of times on a solved cube would make it eventually return to its solved state.

This problem seems impossible right? At the very least, it probably involves some uni graph theory concept and stuff right? Before you close off (pls dont), the solution to this problem requires no prerequisites, just a grasp of logic.


Ok, here comes the solution:

To tackle this problem, I will be using this technique called “Proof by contradiction”.

For instance, if I want to proof that statement A is false, I assume otherwise; that A is true. Then I show that if A is true, absurd shit that doesn’t make sense would happen (ie. we would see a contradiction). Since A being true causes a contradiction, A must be false. Hence proved that A is false.

Got the general gist of this technique? Cause this would be fundamental in our proof.

Alright, the actual proof:

Let’s first assume that there exists an algorithm (Let’s call it “f”) that would not cycle. In other words, repeatedly applying “f” on a cube would cause it to always land in a state that it has not been before:

 

Delete.png

 

However, this would imply that a rubix cube has an INFINITE number of different states! This is a contradiction, since it is well known that a rubix cube has a finite number of states (Left as exercise of reader). Since there is a contradiction, we can safely conclude that after applying “f” sufficiently number of times, it would cause the cube to return to a state it was before.

We are not done however, as this conclusion results in 2 possible cases:

delete

Delete.png

Case 1 is where it returns to the solve state (which we want), and Case 2 is where it returns not to the solved state but to some random state within the cycle (which we want to disprove).

To disprove case 2, we employ prove by contradiction again:

Let’s define “f^{-1}” as the inverse algorithm of “f”. In other words:

delete

Basically, “f^{-1}” is an algorithm that REVERSES what “f” does.

So now, what happens if we replace all “f” with “f^{-1}” in the picture for Case 2? Well, it becomes this:

Delete.png

Now we will show how absurd this would be. Notice the box for “State n”. Notice how this diagram implies that applying the algorithm “f^{-1}” on state n would result in 2 possible states (State n-1 and State k). This is absurd because we know that applying an algorithm on a rubix cube will result in only 1 possible state (ie. each state should only point to 1 other state). Hence we have reached a conclusion that Case 2 is IMPOSSIBLE. Which leaves us with Case 1 as the only case that is possible.

Hence, proved, that repeatedly applying any algorithm on a solved Rubixs Cube would cause it to eventually return back to its solved state.


 

An update to the previous post: I have played with the simulator and recorded some of the animations

 

Hoped you enjoyed this post!

 

 

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s