Second Layer Orange/Red on the L or R face Bottom Layer Orange/Red facing downwards
Conjecture: The total score is always even. Induction base : Initial Score is 0, which is even. Induction Hypothesis: The total score is even after k moves.
Induction step : Moves on the U, D, F and B faces do not change the score of each individual cubie. A 90 o move on the L/R face changes the score of all 4 edge cubies moved. Since −1 ≡ 1 (mod 2) --> ±1 ± 1 ± 1 ± 1 ≡ 0 (mod 2) The score is still even after k+1 th move. We conclude that only 1/2 of the permutations have valid edge-orientation by induction. A cycle is a permutation of the elements in a group which maps the elements to each other's positions in a cyclic form, for example, (1 2 3 4) means that 1 goes to the position of 2, 2 goes to the position of 3, and 4 goes back to the position of 1. Each permutation can be represented in cycle notation. Here are a few examples: Parity Cycle Prove: 32 A long-chained cycle can ALWAYS be broken down into a smaller chain of cycles of length 2, e.g. (1 2 3 4) = (1 2) (1 3) (1 4). A cycle of length 2 is called a transposition. More specifically, a n-cycle can be represented by a product of n-1 transpositions. A permutation can be described as even or odd, depending on whether it is be represented by a product of an even or odd number of transpositions 33 . We can prove that permutations on the Rubik's Cube are always even by induction. Induction Base : Empty move = 0 transpositions = even Induction Hypothesis : We assume the permutation after k moves is even. Induction Step : Any 90 o face turn will create two cycles of length 4, for example, F = (FL FU FR FD)(FUL FUR FDR FDL), which can be broken down into (FL FU)(FL FR)(FL FD)(FUL FUR)(FUL FDR)(FUL FDL) (6 transpositions). Therefore, the permutation is still even after k+1 moves. 1) U = (UF UL UB UR) (ULF ULB URB URF) 2) R2 U R U R' U' R' U' R' U R' = (UF UL UR)
32 MIT (2009) The Mathematics of the Rubik’s Cube. Available at: http://web.mit.edu/sp.268/www/rubik.pdf (Accessed: 19 August 2014) 33 Provenza, H. (2009) Group Theory and the Rubik’s Cube. University of Chicago
51
Made with FlippingBook - Online Brochure Maker