IT IS, says mathematician Michael Kleber, 鈥渢he best card trick there is鈥. The trick is not a new one 鈥 it was invented in the 1920s by the recipient of MIT鈥檚 first mathematics PhD, William Fitch Cheney, Jr. But, nearly 20 years after its inventor鈥檚 death, this mathematical illusion is stimulating new ideas in information theory, the backbone of cryptography and telecoms.
So, are you ready? Here鈥檚 an ordinary pack of cards, shuffled into random order. Please choose five cards from the pack, any that you wish. Don鈥檛 let me see their faces. No, don鈥檛 give them to me: pass them to my assistant Esmerelda. She can look at them.
Now, Esme, show me four of the cards. Hmmm 鈥 nine of spades, six of clubs, four of hearts, ten of diamonds. The hidden card, then, must be the queen of spades!
Advertisement
Tumultuous applause.
At first glance, it just seems impossible 鈥 especially to anyone who knows about information theory. To transmit information, you need to encode it in something that can be set in a variety of arrangements. For example, in the binary code used in computing and telecoms, specifying the number 8 requires a minimum of four binary digits, or bits: 鈥1000鈥. And the same principle is true in this card trick. Here, though, the information is not transmitted via a specific ordering of zeros and ones. The only way to do it is by a specific ordering of the cards Esme presents.
But there鈥檚 a problem. There are only 24 ways to order four cards, so, according to information theory, Esme can only pass me one of 24 possible messages. So how can she tell me what that hidden card is of the 48 possibilities remaining?
Aha! Esme has a further option: she gets to choose which card remains hidden. With five cards, at least two must have the same suit. So Esme and I agree that whichever card she shows me first will have the same suit as the hidden card. Since she showed me the nine of spades, the hidden card will be one of the 12 other spades in the pack.
I鈥檓 gaining ground 鈥 or am I? Now there are only three cards that Esme can use to transmit information by selecting their order. And three cards can be presented in precisely six distinct orderings. So Esme is still unable to specify which of the 12 remaining possibilities is the hidden card. Somehow she has to reduce everything to six options. And she can.
Imagine all 13 spades arranged in a circle, reading clockwise in ascending numerical order, with ace = 1, jack = 11, queen = 12, king = 13. Given any two cards, you can start at one of them, move no more than six spaces clockwise round the circle, and get to the other one.
So all that Esmerelda has to do is make sure that the first spade she shows me is the one from which we can reach the other in six steps or less. Then she can use the three remaining cards to convey the necessary number by presenting them in a particular one of the six possible orderings. There are lots of ways to do this, but the easiest is probably to establish a code based on the cards鈥 relative numerical value. If any two carry the same number, they can be ordered by suit. The bridge system 鈥 clubs, hearts, diamonds, spades 鈥 would work.
The three cards she is looking at constitute a smaller value one (S), a bigger one (B), and one somewhere in between (M). By choosing the right order for the second, third, and fourth cards, say SMB = 1, SBM = 2, MSB = 3, MBS = 4, BSM = 5, BMS = 6, Esmerelda can tell me that crucial number between 1 and 6. Remember the five cards we started with: six of clubs, ten of diamonds, four of hearts, nine of spades, queen of spades. There are two spades, so my lovely assistant has to show me a spade first. Which one? Well, reading 9 鈥 10 鈥 J 鈥 Q gets me from the nine to the queen in three steps, whereas Q 鈥 K 鈥 A 鈥 2 鈥 3 鈥 4 鈥 5 鈥 6 鈥 7 鈥 8 鈥 9 takes more than six steps, so that鈥檚 no good. Esmerelda therefore shows me the nine of spades first.
Then she has to show me the remaining cards in whichever order is the agreed code for 鈥3鈥. Using the code above, the correct order is six of clubs, four of hearts, ten of diamonds. Now I can count three steps on from the nine of spades, which takes me to the queen of spades. And that, ladies and gentlemen, is how it鈥檚 done.
It鈥檚 an interesting exercise in the principles of number theory, but perhaps not earth-shattering. So why are mathematicians so interested in this trick?
Well, picking 5 cards from 52 is what mathematicians call a special case. What happens with different numbers? Could you, for instance, pick the hidden card among 5 drawn from a pack of 100 cards? In a generalisation of the trick, suppose the pack contains p cards (still sticking with four suits) and we draw n of them. The assistant shows all but one of the n cards, and the magician works out the final one. How big can p be?
Information theory tells us that the trick is impossible if there are more hands of n cards than there are messages formed by n 鈭; 1 of them. Doing the calculation, we find that p can be at most n! + (n 鈭 1), where n! is shorthand for 鈥渘 factorial鈥, equal to n 脳 (n 鈭 1) 脳 鈥 脳 3 脳 2 脳 1. Work it out, and you find that you can 鈥 in principle at least 鈥 do the above 5-card trick using a pack of 124 cards. With 6 cards drawn, the pack can have up to 725 cards. Picking 7 cards, the pack can have 5046, and with 8 it can have 40,327.
The calculations show only that the trick is in principle possible with these numbers of cards 鈥 that there are enough possible messages to convey the information needed to specify the final card. But magicians need an actual method for doing the trick. This is where more complex information theory ideas (to be precise, the 鈥渕arriage theorem鈥 and the Birkhoff-von Neumann theorem) come in.
Kleber, of Brandeis University in Waltham, Massachusetts, has laid out his route to working out a manageable way to do the trick with 124 cards in a recent issue of The Mathematical Intelligencer (vol 24, p 9) and he can do it 鈥渜uite smoothly鈥, he says. He also reveals that games expert Elwyn Berlekamp of the University of California, Berkeley, has worked out that there鈥檚 enough slack to perform an impressive variant. Berlekamp asks the volunteer to toss a coin as well as pick five cards. After the assistant has shown four cards, he not only predicts the fifth, he also tells the audience whether the coin was heads or tails.
OK, maybe it鈥檚 not the most important bit of maths in the world. It鈥檚 hardly a route to a theory of everything, and probably won鈥檛 revolutionise information transfer. But it does help mathematicians get to grips with important concepts of information theory. Indeed, there are a slew of papers in press about the trick and its variants, and how they expose the value of devising sensible coding methods. These ideas bridge the gap between 鈥渢here must exist some way to do this鈥 and 鈥渉ere鈥檚 a simple method that anyone can use鈥.
The trick also shows that the context in which you are seeking information has a subtle effect on how much information you actually need. It can even render the 鈥渋mpossible鈥 possible. It鈥檚 like magic.