Resurrection Shuffle

MATHEMATICAL RECREATIONS by Ian Stewart

Scientific American, December 1998

Most card games begin with someone shuffling the deck. The aim of shuffling, of course, is to randomize the order in which the cards appear. If the cards are shuffled too perfectly, however, the results are very far from random. This month I will concentrate on one common type of shuffle — or, rather, two very closely related variants — and see what they can be made to do. We will look at the "riffle" shuffle, in which the deck is divided into two equal parts which are then interlaced alternately. (American magicians call it the Faro shuffle, and to English magicians it is the weave shuffle.) Since the parts are equal, the number of cards in the deck should be even. It is possible to consider an analogous shuffle with an odd number of cards, in which one part has one card more than the other, but for simplicity I will mostly ignore this possibility.

Suppose, for sake of argument, that the deck has ten cards, and number them 0–9. Suppose that, to start with, all cards are face down and the deck is arranged in numerical order from the top down:

Cut the deck between 4 and 5 and interlace. You get

if the top card is taken from the top half of the deck, and

if the top card is taken from the bottom half of the deck. The first method is called an out shuffle, the second an in shuffle.

The theory of in and out shuffles was studied in depth by Persi Diaconis (Stanford), Ron Graham (Bell Labs), and Bill Kantor (U Oregon) in Advances in Applied Mathematics 4 (1983) pages 175–196. They also compiled information on the history of card shuffles, some of which I will now summarize. The earliest recorded mention of the riffle shuffle that they found dates from 1726, in a book called Whole Art and Mystery of Modern Gaming, author unknown. In 1843 J.H. Green described the riffle shuffle to Americians in An Exposure of the Arts and Miseries of Gambling, showing how it could be used to cheat at the game of Faro. Magicians learned of the shuffle from C.T. Jordan's Thirty Card Mysteries of 1919. An early riffle-shuffler, the Nebraskan rancher Fred Black, used to practice the technique on horseback, and he worked out a lot of the math for repeated out shuffles of the standard 52-card deck. Many of the main theorems for decks of any size were published by Alex Elmsley, a computer scientist living in London, in 1957. Some of his results were anticipated by the French mathematician Paul Levy in the 1940s, and further results were proved by Solomon Golomb, the inventor of pentominoes™, in 1961.

An out shuffle can be viewed as an in shuffle on a deck with two fewer cards (the top and bottom card of the original deck). To see why, consider the ten-card deck above. If we ignore cards 0 and 9 in the original order

and look at the result of an out shuffle

we see that the cards in between 0 and 9, shown in bold type, have been subjected to an in shuffle, while 0 and 9 have not moved. By the same reasoning, an in shuffle can be converted to an out shuffle by adding two extra cards, one at the top and one at the bottom. For many purposes this connection allows us to consider just one of the two shuffles.

Suppose we take our ten-card deck and repeatedly subject it to an in shuffle. What happens? Does the deck just get more and more jumbled? Here are the results of the first few shuffles:

So although at first the ordering seems to get more jumbled, by the fifth shuffle the entire deck has exactly reversed its order! Clearly five more riffle shuffles will "resurrect" the original order. We conclude that the in shuffle, applied repeatedly to ten cards, cycles repeatedly through just ten different orders. This is a tiny fraction of the 3,628,800 different ways to place ten cards in order.

If you try the same kind of calculation with different (even) sizes of decks, you find that the deck always returns to its original order if the riffle shuffle is repeated sufficiently many times. It is here that group theory makes its first appearance, because it explains why such repetition is inevitable. Figure 1 shows how each card moves when an in shuffle is applied.

Figure 1: How an in shuffle cycles cards in a deck of 10.

For example card 0's place is taken by card 5, card 1's place by card 0, and so on. Following the arrows, we see that the cards take each others' places in the following order:

repeating again from 0. The ten cards form a single cycle, and with each riffle, the cards move one step further along this cycle. Since the cycle contains ten cards, we see that after ten riffles every card returns to its starting point.

The main atypical feature of this deck is that there is just one such cycle. A more typical case is the 8-card deck; see Figure 2.

Figure 2: How an in shuffle cycles cards in a deck of 8.

Now there are two cycles:

repeating from 0, and

repeating from 2. The first cycle repeats after 6 steps, the second after 2. When the first cycle has reached its first repeat, after six steps, the second cycle has repeated for the third time. That is, after six steps both cycles repeat.

However many cards there are, and whatever rule is used to shuffle them, the progress of the cards through the deck can be broken down into a number of such cycles. Why? Start from any card and follow its progress. Since the deck is finite, eventually the card must reach a position it has previously occupied. From that stage on it will repeat its previous moves. A cycle, however, should repeat from the beginning. Can we be sure that when the card first repeats a previous position, it repeats its initial position? The answer is yes, and the reason is that any shuffle is reversible — it can be "undone" by shuffling the cad "back in time." If the first repeat was not the initial position then we could backtrack one step to find an earlier repeat. For similar reasons, a cycle cannot "run into" another one. So every card occurs in exactly one cycle.

Once we know the cycles, there is a simple way to work out how many shuffles it takes for the entire deck to be "resurrected" into its original order. The cycles have various lengths, and each card in that cycle repeats its position after a number of shuffles equal to that length. Take the lowest common multiple of the cycle lengths: then all cycles repeat after that many shuffles — implying that all cards return to their initial position after that number of shuffles. For example, suppose the cycles have length 10 and 14. The cards in the cycle of length 10 return to their original positions at stages 10, 20, 30, 40, 50, 60, 70, and so on. The cards in the cycle of length 14, on the other hand, return to their original positions at stages 14, 28, 42, 56, 70, and so on. The first number common to both sets, the lowest common multiple of 10 and 14, is 70. And on the 70th shuffle all the cards return to their original places.

The in shuffle, then, always repeats, no matter how big the deck may be. But the number of times required for a repeat has no obvious pattern — the fact that a ten-card deck takes ten shuffles to repeat, equal to the size of the deck, is not typical. In fact decks of 4, 6, 8, 10, 12 14, 16, 18, 20, 22, and 24 cards respectively require 4, 3, 6, 10, 12, 4, 8, 18, 6, 11, 20 in shuffles to bring them back to their original order. Although there is no obvious pattern, there is still a pattern. You just have to be a number theorist to spot it! Take the case of 8 cards. Add one to this to get 9. Form successive powers of 2, divide by 9, and work out the remainders:

The remainder equals 1 for the sixth power — and the number of riffles needed to "resurrect" an 8-card pack is 6. Similarly when there are 10 cards we add 1 to get 11, and consider the remainders on dividing the powers of 2 by 11:

We get remainder 1 for the 10th power, and that is the correct number of riffles to resurrect a 10-card deck.

This rule works in general. You don't actually need to perform the calculation in such a laborious way: instead you just start with 2, repeatedly double and find the remainder on dividing by one more than the size of the deck, and keep going until you hit 1. A general result in number theory called Fermat's Little Theorem — discovered by the great French number theorist Pierre de Fermat, more famous for his 'Last Theorem' recently proved so gloriously by Andrew Wiles (Princeton) — implies that this process reaches 1 after a number of steps that is at most the size of the deck.

Because an out shuffle is the same as an in shuffle on a deck with two fewer cards, a similar rule holds for the out shuffle, but now you subtract one from the size of the deck and find remainders upon dividing powers of 2 by that. For a standard 52-card deck, the relevant numbers are 52 for the in shuffle but only 8 for the out shuffle. In his Mathematical Carnival Martin Gardner suggests a practical method for testing out such results, which is to work backwards. It is difficult, even for an expert magician, to perform an exact riffle shuffle once, let alone repeatedly. But working backwards is easy: deal the deck as if to two people and then stack their hands on top of each other. The reverse of an in shuffle is called an in sort, and the reverse of an out shuffle is called an out sort. The number of steps needed to resurrect the original order of the deck is the same whether you shuffle or sort.

Many card tricks exploit regularities of the riffle shuffle. Martin Gardner's article in the August 1998 issue of Scientific American included a riffle-shuffle trick that works even if you perform the riffle badly! Here's one involving an odd number of cards — though it starts with a deck of 20. Hand this deck to your victim, turn your back, and ask him to shuffle them (by any method); then to insert the joker and remember the two cards it went between. Turn round, take the deck — which now has 21 cards — face down. Perform either an in sort or an out sort and let the victim cut the deck; do this again. Open the cards in a fan, holding them so your victim can see their faces but you can't, and ask him to take out the joker. Break the fan at that point, fold up each part and put the two together swapping their order. Perform two out sorts and an in sort, put the deck face down on the table. Ask the victim to name the two cards he remembered. Turn over the top card: it will be one of them. Turn over the entire pack: the bottom card is the other.

The most difficult question answered in the work of Diaconis, Graham, and Kantor is this: what rearrangements of a deck of 2 n cards can be obtained by using arbitrary sequences of in shuffles and out shuffles? The results depend on n in a very curious way. If n is a power of 2, the number of such rearrangements is relatively small (k \, 2^k if n = 2^k). Otherwise, the number of rearrangements is quite a bit larger, but still falls short of the full (2 n)! possibilities. The exact number depends on whether n is of the form 4 m, 4 m + 1, 4 m + 2, or 4 m + 3 for an integer m. Moreover, the cases n = 6 and n = 12 are exceptional and do not follow the otherwise general pattern. If you want the details, read their beautiful paper