Mathematics Awareness Month 2014: Mathematics, Magic, and Mystery
Navigate the Calendar
The Magic of Perfect Shuffles
Mathematician and master shuffler S. Brent Morris demonstrates how perfect shuffles can create order from disorder.
Taking it Further
Why does Dr. Morris remove one card from the deck before starting his eight shuffles? It so happens that the mathematics is slightly simpler when there are an odd number of cards in the deck. So let’s agree to work with a 51-card deck until we get the main ideas (ahem) sorted out, and we’ll return to this question then.
The first order of business is to introduce modular arithmetic. For instance, when working with a 12-hour clock, we perform calculations modulo 12: If it is 8 o’clock and we add 7 hours, the answer is not 15 o’clock, but rather 3 o’clock. In a 12 hour system, 15 is the same as 3. Formally, we write 15 ≡ 3 (mod 12).
Similarly, in a system with 51 cards, we reduce all calculations modulo 51. Begin by numbering the locations of the cards 0–50, from top to bottom. If, for example, we place bottom card on top, then the card in position p moves to position p + 1 (mod 51). Modular arithmetic is a powerful tool for easily keeping track of cards as we move them around.
Here are some challenge problems for you:
- An out-faro shuffle divides the deck into portions of 26 cards (top portion) and 25 cards (bottom portion) and perfectly interlaces the two portions, leaving the top card “out” or on top. Verify that the card originally in position p ends up in position 2p (mod 51) after an out-faro shuffle.
- After two out-faro shuffles, where is each card?
- Verify that after k out-faro shuffles, the card originally in position p moves to position 2^{k}p (mod 51).
- If after k out-faro shuffles, the card in position 1 comes back to position 1, it must be the case that 2^{k} ≡ 1 (mod 51). Calculate 2^{k} (mod 51) for k = 1, 2, ..., 8, and verify that 8 is the first power of 2 congruent to 1 modulo 51. In other words: It takes eight out-faro shuffles to return a deck to its original order!
- On day 15 of Mathematics Awareness Month 2014, the perfect unshuffle was introduced. Is it true that eight perfect unshuffles will restore a deck to its original order?
The Underlying Mathematics
In a deck of 51 cards, number the locations of the cards 0–50, from top to bottom. Consider the following three operations:
- The Simple Cut, C, moves one card from the top and to the bottom of the deck. Cutting a block of k cards from the top to the bottom is the same as performing k simple cuts in succession, and we will denote this C^{k}. The simple cut moves the card in position p to position p – 1:
C(p) ≡ p – 1 (mod 51).
- The Out-Faro Shuffle, O, divides the deck into portions of 26 cards (top portion) and 25 cards (bottom portion) and perfectly interlaces the two portions, leaving the top card “out” or on top. The out-faro shuffle moves the card in position p to position 2p:
O(p) ≡ 2p (mod 51).
- The In-Faro Shuffle, I, divides the deck into portions of 25 cards (top portion) and 26 cards (bottom portion) and perfectly interlaces the two portions, leaving the top card “in” or next to the top. The in-faro shuffle moves the card in position p to position 2p + 1:
I(p) ≡ 2p + 1 (mod 51).
The video at the top of this page gives a “proof by demonstration” that any combination of eight out-faro or in-faro shuffles interspersed with any number of cuts is the same as cutting a block (possibly empty) from the top to the bottom. You can prove it mathematically with the formulas above—or, with practice, you can do it by demonstration!
The number of out-faro or in-faro shuffles required to cycle a deck of N cards (where N is odd) is the smallest number k such that 2^{k} ≡ 1 (mod N). In deciding what size deck to work with, 2^{8} ≡ 1 (mod 51) but 2^{52} ≡ 1 (mod 53), so a 51-card deck is certainly better to work with than a 53-card deck! What’s the smallest (odd) sized deck that cycles in 7 shuffles? 6 shuffles?
With a deck of N cards where N is even, in-faro and out-faro shuffles have different periods. The number of successive in-faro shuffles required to return the deck to its original state is the smallest number k such that 2^{k} ≡ 1 (mod N + 1). So with 52 cards, 52 successive in-faro shuffles are required! The number of successive out-faro shuffles required to return the deck to its original state is the smallest number k such that 2^{k} ≡ 1 (mod N – 1). So with 52 cards, only eight successive out-faro shuffles are needed.
You can watch what happens to a full deck of 52 cards with both in-faro and out-faro shuffles on this simulator. Pushing the Out button performs the out-faro shuffle (like those performed by Dr. Morris).
The mathematics of the faro shuffle, an extensive faro shuffle bibliography going back to 1726, and the details of the results above can be found in S. Brent Morris, Magic Tricks, Card Shuffling, and Dynamic Computer Memories (Mathematical Association of America, 1998). The proof by demonstration in the video is of Corollary 3.7 of Theorem 3.5, pages 45 and 48.
For those with an understanding of group theory, “The Mathematics of Perfect Shuffles,” by Persi Diaconis, Ron Graham, and William Kantor (Advances in Applied Mathematics, Vol. 4, 1983, pp. 175–196) provides an excellent overview.
At a more accessible level, Martin Gardner wrote about perfect shuffles in Mathematical Carnival (Knopf, 1975). See chapter 10, “Card Shuffles.” This book is also included on the CD compilation Martin Gardner’s Mathematical Games: The Entire Collection of His Scientific American Columns on one CD (MAA, 2008).