# Cards Swapping Problem

The 100 integers from 1 to 100 are each written onto 100 index cards, which are then thoroughly shuffled. To put the cards back into their natural ordering, the only operation allowed is for a pair of cards to be swapped. Is it always possible to put the 100 cards back in order using 74 or fewer of these swap operations?

-
Here is a hint: given any element $p$ of the symmetric group $S_{100}$ (that is, the set of all permutations of $100$ letters), what is the minimum number of swaps needed to generate $p$? This might help: en.wikipedia.org/wiki/Symmetric_group. – William Jan 8 '12 at 17:04

Given a permutation of the cards, an orbit is a collection of cards one can reach from a given starting card by going to its original position, considering the card there, and repeating this any number of times. The shuffled deck is so partitioned into a number of orbits; in its original position every card is an orbit in itself ($100$ different orbits), but with the top card moved to the bottom, the whole deck is a single long orbit.
The main point of the argument is that interchanging any pair of cards changes the number of orbits by $\pm1$: if the two cards belonged to the same orbit, it will split in two, and if they belonged to different orbits the two are glued together into one orbit. These statements are easy to verify, making a schematic drawing of the situation may help. Since the number of orbits changes by only $1$ at each step, it is impossible to go from a situation with just one orbit to one with $100$ orbits in less than $99$ swaps.
@WNY: No my argument does not say or use that the cards swapped must be adjacent. The backward ordering has $50$ orbits so it is natural that one should need $100-50=50$ moves for it. But try to do the cyclic rotation I described in less that $99$, you can't. – Marc van Leeuwen Jan 8 '12 at 18:08
@WNY: No, he is answering the correct question, where swapping any pair of cards is allowed. His answer depends on the cycle decomposition of the permutation, and the fact that swapping any pair of cards can only change the number of cycles by $\pm 1$ ($+1$ if they were in the same cycle). Any rotation has a single cycle in its decomposition; the target state has $100$ cycles; so you need at least $99$ swaps to get from one to the other. The backward ordering, on the other hand, has $50$ (length $2$) cycles, so you could (and can) get from it to the target state in $50$ moves. – mjqxxxx Jan 8 '12 at 18:42