A perfect in-shuffle of a deck of 52 cards is defined as follows. The deck is cut in half followed by interleaving of the two piles. So if the cards were labeled 0, 1, 2, ..., 51, the new sequence is 0, 26, 1, 27, 2, 28, ... With repeated in-shuffles, shall we ever get back the original order? In how many iterations?

From William Wu's CS Puzzles Page

The shuffling technique described in the puzzle is known as the Faro Shuffle (wikipedia).

First, let us convince ourselves that we shall get back the original order. The 'inverse' of the perfect in-shuffle is unique. In other words, there is only one other card ordering that would result in a given card ordering with the application of the perfect in-shuffle. So by repeated application of the perfect in-shuffle, we are certain to recover the original ordering because the total number of card orderings is finite: 52!.

A closer look at the structure of the perfect in-shuffle reveals that it is simply a permutation. Let the cycle lengths of the permutation be c1, c2, c3, ... Then the number of iterations is the LCM of c1, c2, c3, ... With 52 cards, let the cards be labeled 0, 1, 2, ..., 51. Then cutting and interleaving results in 0, 26, 1, 27, 2, 28, ... , which is equivalent to the following "moves": { 0 -> 0, 1 -> 2, 2 -> 4, 3 -> 6, 4 -> 8, ..., 26 -> 1, 27 -> 3, 28 -> 5, 29 -> 7, ... 51 -> 51}. The inverse of these moves can be captured succinctly as follows: If i is even, i --> i/2. If i is odd, then i -> 26 + (i-1)/2. The formula allows us to list the cycles of the permutation in reverse order:

(length 1) 0 -> 0

(length 1) 51 -> 51

(length 8) 50 -> 25 -> 38 -> 19 -> 35 -> 43 -> 47 -> 49 -> 50

(length 8) 48 -> 24 -> 12 -> 6 -> 3 -> 27 -> 39 -> 45 -> 48

(length 8) 46 -> 23 -> 37 -> 44 -> 22 -> 11 -> 31 -> 41 -> 46

(length 8) 42 -> 21 -> 36 -> 18 -> 9 -> 30 -> 15 -> 33 -> 42

(length 8) 40 -> 20 -> 10 -> 5 -> 28 -> 14 -> 7 -> 29 -> 40

(length 2) 34 -> 17 -> 34

(length 8) 32 -> 16 -> 8 -> 4 -> 2 -> 1 -> 26 -> 13 -> 32

So the answer is LCM of {1, 2, 8}, which is 8 shuffles!

Alternate Solution (submitted by Vivek in Oct 2010 in a comment) For all cards other than 0 and 51, a card at position p gets shuffled to position 2p mod 51, which a function that maps [1, 50] → [1, 50]. After n shuffles, a card at position x would move to position (2ⁿ p) mod 51. Consider some p in [1, 50] that is co-prime to 51 (in other words, p and 51 have no common prime factors). Then the smallest n > 0 such that 2ⁿ mod 51 equals 1 happens to be 8 (because 2ⁿ mod 51 for n ranging from 1 thru 8 is the sequence 2, 4, 8, 16, 32, 13, 26, 1). Now consider the two prime factors of 51, namely 3 and 17. The smallest n > 0 such that (2ⁿ ⋅ 3) mod (17 ⋅ 3) equals 3 is also 8 (because 2ⁿ mod 17 for n ranging from 1 thru 8 is the sequence 2, 4, 8, 16, 15, 13, 9, 1). Finally, the smallest n > 0 such that (2ⁿ ⋅ 17) mod (3 ⋅ 17) equals 17 is 2 (because 2ⁿ mod 3 for n ranging from 1 thru 2 is the sequence 2, 1). Thus every card would return to its own position in at most 8 shuffles.

1) Is there a closed form for the number of shuffles in terms of n, the number of cards? Those familiar with group theory might want to read The Mathematics of Perfect Shuffles by Persi Diaconis, R L Graham and William M Kantor, Advances in Applied Mathematics (4), p 175-196, 1983. Further information: Faro Shuffle (wikipedia).

2) The Korn Shell Puzzle is related: