Induction Ill The horizontal lines indicate sequences of elements. Swapping c and y gives the permu tation: y b1.. bk This reverses the order of 2k +l pairs: a and y, a and each bi, and y and each b;. Effectively, this flips the parity 2k 1 times which is equivalent to flipping the parity once Lemma 3. Rotating three terms in a permutation preserves the parity of the number of inversions Proof. Take an arbitrary permutation A forward rotation is equivalent to swapping y and z and then swapping r and z y Similarly, a reverse rotation is equivalent to swapping and y and then r and z: In any case, two swaps flip the parity twice, which leaves the original parity unchanged Theorem 4. No sequence of moves transforms the original configuration of the 9-Number Puzzle into the transpose configuration Proof. We use induction. Let P(n) be the proposition that after n steps the number of inverted digits is even Base case. After 0 steps, the puzzle is in the original configuration. There are zero inver- sions, so P(0) is true Inductive step. Suppose that after n steps, the puzzle has an even number of inversions By Lemma 3, rotating three digits preserves the parity of the number of inversions. Thus, the puzzle has an even number of inversions after n+ l steps as well By the principle of induction, P(n) is true for all n 20; that is, the number of inversions is even after any sequence of moves. The transpose configuration is unreachable since it has an odd number of inversions A few wrap-up notes, First, notice that Lemma 3 holds when any three digits are ro- tated. Thus, even if we allowed rotations along the long diagonals of the 9-Number Puz zle, there would still be no way to reach the transpose configuration. Second, similar rguments about permutations and inversions explain why certain states are unreach able in many other puzzles. For example, you may have observed that there is no way to flip a single edge of Rubiks Cube. Finally, you might be discouraged that this technique only helps prove that puzzles are not solvable. This seems rather negative. But remember in that in the context of a file system or communication protocol, proving that the system never enters a corrupted or deadlocked state is a very good thingInduction III 7 The horizontal lines indicate sequences of elements. Swapping x and y gives the permu￾tation: y b1 . . . bk x This reverses the order of 2k+1 pairs: x and y, x and each bi, and y and each bi. Effectively, this flips the parity 2k + 1 times which is equivalent to flipping the parity once. Lemma 3. Rotating three terms in a permutation preserves the parity of the number of inversions. Proof. Take an arbitrary permutation: x y z A forward rotation is equivalent to swapping y and z and then swapping x and z: z x y Similarly, a reverse rotation is equivalent to swapping x and y and then x and z: y z x In any case, two swaps flip the parity twice, which leaves the original parity unchanged. Theorem 4. No sequence of moves transforms the original configuration of the 9­Number Puzzle into the transpose configuration. Proof. We use induction. Let P(n) be the proposition that after n steps the number of inverted digits is even. Base case. After 0 steps, the puzzle is in the original configuration. There are zero inver￾sions, so P(0) is true. Inductive step. Suppose that after n steps, the puzzle has an even number of inversions. By Lemma 3, rotating three digits preserves the parity of the number of inversions. Thus, the puzzle has an even number of inversions after n + 1 steps as well. By the principle of induction, P(n) is true for all n ≥ 0; that is, the number of inversions is even after any sequence of moves. The transpose configuration is unreachable since it has an odd number of inversions. A few wrap­up notes, First, notice that Lemma 3 holds when any three digits are ro￾tated. Thus, even if we allowed rotations along the long diagonals of the 9­Number Puz￾zle, there would still be no way to reach the transpose configuration. Second, similar arguments about permutations and inversions explain why certain states are unreach￾able in many other puzzles. For example, you may have observed that there is no way to flip a single edge of Rubik’s Cube. Finally, you might be discouraged that this technique only helps prove that puzzles are not solvable. This seems rather negative. But remember in that in the context of a file system or communication protocol, proving that the system never enters a corrupted or deadlocked state is a very good thing!