Card Shuffling
12 Sep 2008
Puzzle

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?

Source
Solution

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 (2n 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 2n mod 51 equals 1 happens to be 8 (because 2n 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 (2n ⋅ 3) mod (17 ⋅ 3) equals 3 is also 8 (because 2n 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 (2n ⋅ 17) mod (3 ⋅ 17) equals 17 is 2 (because 2n 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.

Followup

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:

You are sitting at a computer terminal whose 26 alphabetic keys have been randomly rearranged (permuted) and you enter your name, say, "Mike Korn." Since the keys are scrambled what appears on the screen is also scrambled. The game consists of you typing the characters you see on the screen until your name appears. The length of the game is the number of times you must type a the string on the screen before your name appears, at which point the game terminates.
1. Is every possible game guaranteed to terminate in a finite number of steps?
2. How does the length of game vary with respect to the two inputs, i.e., the name and the permutation?
3. If every game does terminate in a finite number of steps, what is the longest game?
The last question asks for the permutation whose LCM of cycle lengths is maximized. This quantity is also known as Landau's Function; its natural log asymptotically converges to $latex \sqrt{n \log n}$.