8 perfect shuffles

It is said that 8 perfect shuffles of a standard deck of 52 cards results in an unshuffled deck. Why is that? Is it true only for 52 cards? What kind of shuffle is implied by this statement? Yesterday, we (high school math buddies) made pretty good sense of it.

Let’s first index positions in a standard deck by 0,1,…,51.

When we say “perfect shuffle,” it means to cut the deck in half, then interleave the cards from the two halves. There are actually two choices here, depending on which card we put on top. We can send card 0 to 0, card 26 to 1, card 1 to 2, …, card 25 to 50, card 51 to 51 (we’ll call this Shuffle 1), or we can send card 26 to 0, card 0 to 1, card 27 to 2, …, card 51 to 50, card 25 to 51 (we’ll call this Shuffle 2). Shuffle 1 is what we deal with, because the statement doesn’t work for Shuffle 2. But note that Shuffle 2 is just Shuffle 1 followed by exchanges of pairs.

So, the effect of shuffling on the first half of the deck (\(n \in \{ 0, \dots ,25 \}\)) is to send card \(n\) to \(2n\). Notice that a perfect shuffle looks the same if we flip the deck around, so the effect on the second half of the deck (\(n \in \{26, \dots ,51 \}\)) is to send card \(n\) to \(R(2R(n))\), where \(R(n) = 51-n\) is the operation that gives the reversed index of card \(n\).

\(R(2R(n)) = 51 – 2(51-n) = 2n – 51\). Thus each shuffle sends card \(n\) to \(2n\), except that sometimes, we subtract 51 from the answer. (That “sometimes” is when the card \(n\) is in the second half of the deck.) The point is, no matter what, the card \(n\) is again sent to something in the range 0,…,51, so in fact it is sent to \(2n\ (mod\ 51)\) (if we ignore 51, which is basically 0, and is always sent to itself.)

If we shuffle \(s\) times, we get that card \(n\) is sent to \(2^s n\ (mod\ 51)\).

Immediately, we see that 8 shuffles works because \(2^8 n \equiv n\ (mod\ 51)\), and

In general, \(s\) shuffles brings a deck of size \(d\) back to its original order if and only if \((2^s – 1) n \equiv 0\ (mod\ d-1)\) for all \(n\in \{0,\dots,d-1\}\), that is, if and only if \(d-1\) divides \(2^s – 1\).

The last statement is because if \((2^s -1) n \equiv 0\ (mod\ d-1)\) for \(n=1\), then it must be true for all \(n>1\). (The case \(n=0\) is trivial.)

There are more interesting observations. If \(s\) shuffles brings a deck to its original order, then surely \(ks\) shuffles does that, too. And indeed, if \(d-1\) divides \(2^s – 1\), then it also divides \(2^{ks} – 1\), which factors as \((2^s – 1)(2^{(k-1)s} + 2^{(k-2)s} + \cdots + 2^s + 1)\).

In another observation, we can explicitly write the card position after \(s\) shuffles as

\(2(\dots 2(2n – 51 b_1(n)) – 51 b_2(n) \dots) – 51 b_s(n)\ \ \ \ (*)\)

where \(b_i(n)\) is an indicator bit that is 1 if, entering the \(i\)th shuffle, the card is in the second half of the deck, and 0 otherwise.

Expanding \((*)\), we get \(2^s n – 51 (2^{s-1} b_1(n) + 2^{s-2} b_2(n) \cdots 2^1 b_{s-1}(n) + 2^0 b_s(n)) \)

Now, define \(b(n) \equiv 2^{s-1} b_1(n) + 2^{s-2} b_2(n) \cdots 2^1 b_{s-1}(n) + 2^0 b_s(n)\). Clearly, \(\overline{b_1(n) b_2(n) \dots b_s(n)}\) is the binary expansion of \(b(n)\).

So \(s\) shuffles brings the deck back to its original order if and only if \(2^s n – 51 b(n) = n\) for all \(n\), i.e. \(b(n) = \frac{2^s – 1}{51}n\). But we know that 51 divides \(2^s – 1\) in our example, so \(\frac{2^s – 1}{51}\) is an integer, and in general

If \(s\) shuffles brings a deck of size \(d\) to identity, then the integer given by \(\frac{2^s – 1}{d – 1} \equiv b(1)\) defines the function \(b(n)\) for all \(n\) by \(b(n) = n b(1)\), where the binary expansion of \(b(n)\) gives which half the card \(n\) is in for all \(s\) shuffles.

In the case of \(s=8\) and \(d=52\), \(b(1) = 5\).

Now we can also find the minimum number of shuffles to return various deck sizes to identity, by looking at the factors of \(2^s-1\):

\(s\): \(d\) for which \(s\) is minimal
1: 2
2: 4
3: 8
4: 6, 16
5: 32
6: 10, 22, 64
7: 128
8: 18, 52, 86, 256

etc…

Of course, every deck of size \(d\) can be returned to its original order in some number of shuffles: at most \(d!\) (and if fewer, then the number of shuffles divides \(d!\)), this is because the automorphism group of \(d\) elements is at most size \(d!\). This knowledge is of no practical utility, since \(d!\) is huge, but it does imply that any odd positive integer \(d-1\) divides \(2^{d!} – 1\). And, it highlights the fact that some deck sizes are very special: any \(d\) that is a power of 2 only takes \(\log d\) shuffles, surely; but especially 52, for such a large deck size that isn’t a power of 2, the fact that it only takes 8 shuffles is quite amazing.

I do wonder if there are any “bad” deck sizes \(d\) that do take up to \(d!\) shuffles to return to the original order. A search of the factors of Mersenne numbers may be in order.

Comments

  1. Rits
    December 30th, 2010 | 16:10

    Hey,
    Can you help me with this problem?

    A new deck of cards is in the standard order from the top: ace of spades,
    deuce of spades, three of spades…until king of spades. After that all the diamonds follow in the same order, then all the hearts, then clubs.
    Finally, there are two jokers on the bottom. After performing 16 perfect shuffles, what number is on the top card now?

  2. me
    March 23rd, 2011 | 16:27

    If these 16 shuffles are in-shuffles, where the first card goes on top each time, then the top card is the same all the time, and there would be no problem to solve.

    So let’s assume you’re talking about out-shuffles, where the first card in the second half of the deck goes on top. For this, you apply a modified version of the first result from the post. Card n in the deck is sent to 2^s*(n+d/2) (mod d-1) in this case. So you are solving 2^16*(n+27) = 0 (mod 53) for n in {0,…,53}, the solution of which is n = 26.

    This corresponds to the first card of the third suit, so in your case the ace of hearts.

Leave a reply