Parity Theorem for Permutations - The Reduction Algorithm Rules and the Proof

John O. Kiltinen

In the demonstration program, the computer performs a shortening algorithm that is based on a simple idea. Since starts with all markers in their home boxes, performs a sequence of transpositions, and eventually returns every marker to its home box, the first marker moved is eventually going to be brought home. There is a potential for shortening the sequence of transpositions by eliminating the transposition that moves this first marker away and the transposition that moves it back home.

To produce a shortening algorithm built on this idea, all one needs is to devise rules for modifying the sequence of transpositions to adjust for the elimination of the two transpositions we have identified. We will set forth some rules that meet this objective. Building on our hands-on experience with the demonstration program, let us state the rules for the algorithm in terms of the computer’s response with the blue markers to the transpositions that the human user performs with the green markers.

  1. When the human does the first swap, the computer does not do one. Instead, it makes note of the first marker the human moved, and labels the box from which it came as the “First Box, ” and tags the other box involved in this swap, and calls it the “Tagged Box”. (The First Box will remain fixed throughout this procedure, but the box designated as the Tagged Box may change.)

  2. The computer responds to subsequent swaps of green markers on the left by the human by doing swaps of its set of blue markers on the right, using the following rules:

    1. If the human’s green swap involves neither the First Box nor the Tagged Box, the computer does its swap between the same two boxes.

    2. If the green swap involves the Tagged Box but not the First Box, the blue swap is between the same two boxes, but the computer also moves the tag, so as to keep it with the green disk from the First Box.

    3. If the green swap involves the First Box but not the Tagged Box, the computer does a swap between the Tagged Box and the other box, not the First, that the human used.

    4. If the green swap involves both the First Box and the current Tagged Box, the computer does not do any swap.

  3. Once case d of step 2 has happened -- which it must since the first green marker moved is always in the Tagged Box and the first person is eventually going to bring it back home -- the computer does all subsequent swaps between the same boxes as the human.

If one follows the procedure described here, it will produce a modified truncated sequence of transpositions that has two fewer transpositions at the point that the original sequence returns the first marker moved to its home box. Since the modified truncated sequence is the same as the original one from that point on, it uses two fewer transpositions in the end when each has returned all of the markers to their home boxes.

You may wish to work out the proof that this algorithm leads to the Reduction Lemma on your own, or you can follow this link for a proof.