The question asked you to show that it is possible to permute a list however you like using only successive swaps, and that any two lists of swaps that achieve the same permutation contain either both an even number of swaps or both an odd number of swaps.
Part one: You can get the Rockettes in order no matter how they come out on stage
Here’s an algorithm for doing it:
- If the Rockette who should be first is not first, switch her with the first one.
- If Rockette who should be second is not now second, switch her with the second one.
- Continue until you get to the last two Rockettes. All the Rockettes ahead of them are in place, so the last two are in the last two spots. If they’re in the wrong order, switch them, and you’re done.
Part two: A permutation has a well-defined parity (even/odd quality).
Slap a number on each of the Rockettes so that when they’re in the right order they’ll line up as (for four dancers) 1,2,3,4
As the dancers come out on stage, they’re in some random order, like 3,1,4,2
Taking that random order, we’ll calculate a number called the parity in the following way:
Take each possible pair of dancers. That makes n(n-1)/2 pairs. We’ll be assigning each of those pairs a number. If the dancer with a higher number comes later in the lineup, give that pair a one. If the dancer with the higher number comes earlier, give that pair a minus one. Multiply all the n(n-1)/2 ones and minus ones together to get a final one or minus one for the entire lineup. All of the n! possible lineups now have either a minus one or plus one associated with them through this procedure. That plus or minus one is called the lineup’s “parity”.
I’ll calculate the parity for the example order 3,1,4,2
1*-1*1*-1*-1*1 = -1
The parity of 3,1,4,2 is odd.
Lemma: Any time you swap two dancers, you go from one lineup to a new lineup. Those lineups have opposite parity, as defined above.
Proof: Since the parity comes from multiplying numbers associated with pairs of dancers, we’ll try to find all the pairs whose numbers could flip due to the switch of dancers. Switching the dancers changes the pair of those two dancers. It does not change the pair of any two dancers who weren’t involved in the switch. It also does not change the pair of any dancer who was behind both of those switched, or in front of both of those switched. However, for each dancer in the middle of the two who were switched, that dancer’s pair with each of the two who were switched gets multiplied by minus one. So all told, the number of pairs whose +/-1 gets flipped is one for the pair of the two switched dancers, and two for the each dancer in the middle of them. The two flips for the pairs for the dancer in the middle cancel each other out in the final product, so the switch of two dancers ultimately gives a lineup whose parity is opposite that of the original lineup.
For example, if I take 3,1,4,2 and switch the 1 and 2, I get 3,2,4,1. The pairs change as follows:
(1,2) 1 -> -1
(1,3) no change
(1,4) 1 -> -1
(2,3) no change
(2,4) -1 -> 1
(3,4) no change
So all together, there were three flips, and the total parity goes from -1 to 1.
Now suppose the dancers come out on stage in a permutation whose parity is plus one. We already proved that by making some switches, we can get them back to the correct starting order. If we make an odd number of switches, we’d change the parity an odd number of times, leaving it as minus one. But the correct order has parity plus one, so no odd number of switches can get us there, and the total number of switches to solve the problem must be even. Similarly, if they come out on stage in a permutation with parity minus one, we’ll have to make an odd number of switches to get them to the plus-one-parity correct order.
That means that if the Rockettes come out on stage messed up, but you can find a way to get them in order with an even number of switches, you’ll never find a way to put them back as they were and do it again with an odd number of switches.