| | Ivars Peterson's MathTrek |
August 3, 1998
S. Brent Morris likes to say that he's the only person with a doctorate in card shuffling. A mathematician at the National Security Agency (the world's largest employer of mathematicians) in Fort Meade, Md., he is also a showman, specializing in card tricks. Morris demonstrated a number of feats of legerdemain at last month's Mathfest in Toronto.
In one trick, the magician tosses a new deck of cards into the audience, where it is caught by someone, whose name turns out to be Susan. She shuffles the deck several times and chooses one card. The magician then pulls out of his pocket an "invisible pen." He hands it to Susan and tells her to "sign" the back of the card, then show it to the other spectators. She reassembles the deck and hands it back to the magician.
"Let me get your card thoroughly lost in the deck," the magician says. "A mathematician once told me there are several ways to shuffle cards--riffle, overhand, Hindu, and so on--but he preferred the perfect shuffle. The perfect shuffle takes a little practice to master, but it does a superior job of mixing the cards."
The magician shuffles the cards several times, ending with three perfect shuffles. To find Susan's card, he returns the deck to its case and tosses it to a randomly selected member of the audience. He asks for the recipient's name and finds out it is Dave.
"Dave, thanks for volunteering. Take the deck out of the case and deal one card for each letter in your name. The next card in the deck, the one at which you stopped dealing, has Susan's 'invisible signature' on the back. Please turn it over and show it to the audience."
Tumultuous applause and cheering.
Morris reveals how this card trick works and explains the mathematics of perfect shuffles in his new book Magic Tricks, Card Shuffling, and Dynamic Computer Memories.
The last part of the trick hinges on finding someone in the audience whose name is four or five letters long. If the person receiving the deck doesn't qualify, the magician can always ask him to toss it to someone else ("to make the selection even more random") until the right number of letters is present in a recipient's name. That's a pretty good bet because 60 to 80 percent of common American first names have four or five letters. That may not necessarily be true in another country.
This also means that the magician must have orchestrated his shuffles to bring Susan's card into the fifth position from the top of the deck. That's where knowledge of the perfect shuffle comes in.
To achieve a perfect shuffle, the deck is divided exactly in half, and the cards of the two halves are alternately interleaved. That can be done in two ways. Consider a deck of eight cards, numbered from 1 to 8 and divided into two halves, 1 2 3 4 and 5 6 7 8. In an in-shuffle, a deck originally arranged as 1 2 3 4 5 6 7 8 would become 5 1 6 2 7 3 8 4. In an out-shuffle, the final arrangement would be 1 5 2 6 3 7 4 8.
It turns out that an ordinary deck of 52 cards is returned to its original order after eight out-shuffles. It's also possible to move the top card of a deck to any location by using the right combination of in- and out-shuffles.
Count the top card as position 0. To move the top card to any position in the deck, express that position as a binary number. Starting from the left, perform a perfect shuffle for each digit in the binary number--an out-shuffle for 0 and an in-shuffle for 1.
For example, to move a card into position 14 (fifteenth card from the top), express 14 as a binary number: 1110. Three in-shuffles and one out-shuffle, in that order, bring the top card into position 14. Similarly, in the card trick, position 4 (fifth card from the top) is 100, so the magician performs one in-shuffle, followed by two out-shuffles.
That still leaves the delicate problem of making sure that the original top card is the one that Susan chose. This preliminary step requires some sleight of hand, which Morris reveals in his book.
Morris was first attracted to magic when he saw a trick performed on the Howdy Doody Show, a popular children's television program of the 1950s. "I was amazed. I was enthralled. I was hooked," he declares. "My life's career was set--I was going to be a magician!"
That was the inspiration for a career that ended up entangling magic and mathematics. A graduate term paper describing the card-placement trick led to his first publication, to research on permutation matrices, and eventually to his doctorate.
The experience became a striking demonstration of how seemingly different problems often involve the same underlying mathematics. The mathematics of perfect shuffles, for example, comes up in the theory of parallel processing and in the design of computer memories.
"After graduating from Duke, my first assignment as a professional mathematician led me back to card shuffling," Morris says. "Glenn Stahley, my supervisor, showed me an article from IEEE Transactions on Computers in which perfect shuffles had been used to design a computer memory. I instantly recognized my favorite card-placement trick but in an unexpected setting."
The research produced an article and a patent for a novel type of dynamic computer memory.
Copyright 1998 by Ivars Peterson
References:
Diaconis, P., R.L. Graham, and W.M. Kantor. 1983. The mathematics of perfect shuffles. Advances in Applied Mathematics 4:175.
Gardner, M. 1989. Card shuffles. In Mathematical Carnival. Washington, D.C.: Mathematical Association of America.
Kolata, G. 1985. Prestidigitator of digits. Science 85 6(April):66.
______. 1982. Perfect shuffles and their relation to math. Science 216:505.
Morris, S.B. 1998. Magic Tricks, Card Shuffling, and Dynamic Computer Memories: The Mathematics of the Perfect Shuffle. Washington, D.C.: Mathematical Association of America.
Peterson, I. 1990. Islands of Truth: A Mathematical Mystery Cruise. New York: W.H. Freeman.
______. 1984. Mathematical shuffling. Science News 125(March 31):202.
The definition of a perfect shuffle can be found at http://www.astro.virginia.edu/~eww6n/math/RiffleShuffle.html.
Comments are welcome. Please send messages to Ivars Peterson at ipeterson@maa.org.