Problem:
Karl starts with cards labeled lined up in a random order on his desk. He calls a pair of these cards swapped if and the card labeled is to the left of the card labeled . For instance, in the sequence of cards , there are three swapped pairs of cards, , and .
He picks up the card labeled 1 and inserts it back into the sequence in the opposite position: if the card labeled 1 had cards to its left, then it now has cards to its right. He then picks up the card labeled 2 and reinserts it in the same manner, and so on until he has picked up and put back each of the cards exactly once in that order. (For example, the process starting at would be .)
Show that, no matter what lineup of cards Karl started with, his final lineup has the same number of swapped pairs as the starting lineup.
Solution:
First solution. Consider the following alternative procedure: When Karl removes the card labeled 1 , before he inserts it, he adds to its label to make it a card labeled . Then he reinserts the card as in the original procedure. Now, the new arrangement of cards has the same number of swapped pairs as before, since the 1 used to be part of swapped pairs using the cards to its left, and now the is part of swapped pairs using the cards to its right.
By the same argument, if he next removes the card labeled 2 and adds to its label before reinserting it in its new position, and so on, he ends up with a permutation of that has the same number of swapped pairs as the one he started with. But this permutation clearly corresponds to the ending permutation from Karl's original procedure upon subtracting from all the labels, and this subtraction doesn't change the number of swapped pairs. This completes the proof.
Second solution. At each moment during the procedure, define the "charge" on a card to be the net (positive or negative) number of steps it would take to the left if it were to be moved next. The charge depends only on the card's location. For example, if there are 4 cards, their charges from left to right are .
At each stage, let be the number of swapped pairs, and let be the sum of the charges on all of the cards that have not yet moved. We claim that each move leaves unchanged. To see this, suppose that card is being moved steps to the left. (We take to be positive; the case of negative is similar.) When card passes a lower-numbered card, this creates a swapped pair, increasing by +1 . When card passes a higher-numbered card, it removes a swapped pair, thus changing by -1 ; but it also moves the higher-numbered card one step to the right, increasing its charge (which is included in ) by +2 . Thus the net increase in is again +1 . So the total effect of passing cards is to increase by . But also, after we move card , its own charge (which was ) is no longer included in . So on balance, is unchanged.
So is unchanged by the entire process. But is zero at the beginning of the process (all the charges sum to zero, by symmetry), and also at the end (when is just the empty sum). So , the number of swapped pairs, is also the same at the beginning as at the end. This is what we needed to prove.
The problems on this page are the property of the MAA's American Mathematics Competitions