Riffle Shuffles and a Good Nap

I was travelling to Manipal by bus with a few friends and although everyone else was in a sleepy and relaxing mood, I was hell bent on exchanging puzzles and putting my grey cells to use. My friend Abhishek wanted to catch up on his sleep (he'd flown in from Kolkata just that morning after writing his final exams at IIMC) and was not amused by my enthusiasm :D He immediately put me to work by asking a seemingly innocuous question. His objective was achieved as I spent the next hour twirling my hair and racking my brain for an answer, while he took a much needed map.

I present the question here and provide a neat solution as well.

By performing a perfect riffle shuffle we completely change the order of cards in the deck (almost a perfect derangement). But if we keep repeating the action, can we ever return to the exact same original order? If so, after how many repetitions and if not, why not?


At first glance, the problem seems very difficult, but upon closer examination there is a pattern to the madness and the mathematics is really quite simple.

Let the starting order of cards be denoted by O1. Then after one riffle shuffle, the new order is O2. Clearly the original order O1 completely defines O2. Similarly the order O2 can be acquired only from the unique starting order of O1. Successive repetitions will generate new orders, but due to the limited number of possible order (52!), we will encounter a repetition of order at some point. Now we need to find the cycle of repetition.

If we denote the original starting order as


1,2,3,4......26,27,28....50,51,52

then after one riffle shuffle we get

1,27,2,28,3,29

Thus we have the mapping

1 -------->1
2 -------->3
3 --------> 5
..................
27 --------> 2
28 --------> 4
29 --------> 6

For the first half the transformation is clearly n -------> 2n-1
The trick is to spot the transformation for the second half which is n --------> (2n-1) mod 51

Thus without loss of generality, we can take the transformation of any "n" to be
F(n)  = (2n-1) mod 51

Let the cycle of repetition be N.

Then we have the equation
F(F(F(....(n))....)))  N times = n              ---------------------------------------- (1)

After expanding F(F(n)) and then F(F(F(n))) and observing the pattern, we can rewrite (1) as

(2^N-1)(n-1)=51k

This means if the cycle of repetition is "N", then for any card position "n" from 1 to 52, the left hand side should be of the form 51k, where k is a Natural number.

By inspection, we see that N=8 yields 255 as a factor on the LHS and this divides 51 wholely.

Thus the answer is 8 repetitions, to regenerate the same order.