Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
1  
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
add comment

1 Answer

up vote 5 down vote accepted

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.

share|improve this answer
    
@WNY: I don't get your point. Certainly the cards are in a linear order after shuffling (if they were in a circle, say, then they would remain so after each swap and there is no hope of getting the natural, linear, order). And there is no "reading" implied in my answer; you may stare at the cards forwards and backwards and sideways as much as you like, but the only move allowed is swapping two cards. –  Marc van Leeuwen Jan 8 '12 at 17:58
    
@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
1  
@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
    
Yes, of course! My apologies. –  William Jan 8 '12 at 18:57
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.