Waste less time on Facebook — follow Brilliant.
×

Rubik's Cube Proof

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

In other words, supposed the algorithm is to turn the top side once. After repeating this algorithm 4 times, the cube would be returned to its solved state. 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 tough. However, the solution to this problem requires no prerequisites, just a grasp of logic.


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 stuff 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. It works the other way too; proving A is true.

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:

However, this would imply that a rubik's cube has an INFINITE number of different states! This is a contradiction, since it is well known that a rubik's cube has a finite number of states (Left as exercise of reader). Since there is a contradiction, we can safely conclude that there exists no such \(f\).

The above conclusion results in 2 possible cases:

Where the cube eventually returns to the solve state (which we want)

Where the cube returns not to the solved state but to some random state within the cycle (which we want to disprove).

To disprove Case 2, Proof by Contradiction can be applied once again. Let \(f^{-1}\) be the inverse algorithm of \(f\). Basically, \(f^{-1}\) reverses what \(f\) does to the cube:

Now we replace all \(f\) with \(f^{-1}\) in Case 2.

Focus on "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 rubik's 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.

Note by Julian Poon
1 week, 4 days ago

No vote yet
1 vote

Comments

Sort by:

Top Newest

In group theory, the group generated by repeated application of an action is called the cyclic group of that element. The number of times one has to apply an action to itself to get back the identity is called the order of the element. This can have interesting applications.

Here is a fun problem on the Rubik's Cube asking you to compute the order of certain elements of the Rubik's Group, Agnishom Chattopadhyay · 2 days, 22 hours ago

Log in to reply

@Agnishom Chattopadhyay Nice! Thanks for that information! Julian Poon · 1 day, 19 hours ago

Log in to reply

This reminds me of the cyclic arguments like showing why the Fibonacci numbers mod n is immediately periodic. I wonder if there is a connection. Chung Kevin · 3 days, 2 hours ago

Log in to reply

@Chung Kevin There is. The same proof technique works. Agnishom Chattopadhyay · 2 days, 22 hours ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...