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?
Cards Swapping Problem
-
1Here 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: http://en.wikipedia.org/wiki/Symmetric_group. – 2019-05-16
1 Answers
No, you may need as many as 99 swaps, and the case where the topmost card is moved to the bottom is one of the (many) cases that requires this number.
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.
-
0Yes, of course! My apologies. – 2012-01-08