Tanya Khovanova's Math Blog

The 5-Card Trick and Information, jointly with Alexey Radul

6th August 2024, 05:27 pm

The famous 5-card trick begins with the audience choosing 5 cards from a standard deck. The magician’s assistant then hides one of these cards and arranges the remaining four cards in a row, face up. On entering the room, the magician can deduce the hidden card by inspecting the arrangement. To eliminate the possibility of secret signals between the assistant and the magician, the magician needn’t even enter the room — an audience member can call them and read out the row of cards.

We will not delve into the mechanics of the trick, which are widely available online. Instead, we will explore the information theory underlying it. Michael Kleber’s paper, The Best Card Trick, provides an information-theoretic argument that works as follows:

For a deck of N cards, the number of different messages the magician can receive is N(N-1)(N-2)(N-3). The magician must guess the hidden card, which is equivalent to determining the set of five cards chosen by the audience. The number of such sets is N choose 5. For the trick to work, the number of messages must not exceed the number of possible answers, leading to the inequality: (N choose 5) ≤ N(N-1)(N-2)(N-3). After some manipulation, we get that (N-4)/120 doesn’t exceed 1. This implies that the deck can have at most 124 cards. The bound turns out to be tight: as discussed in Kleber’s paper, the trick can still be performed with such a huge deck. The paper expands this argument to a trick with K instead of 5 cards and shows that the maximum deck size for such a trick is K! + K – 1.

Here, we want to present a more direct, intuitive argument. We will make the argument for the 5-card trick, which is easily generalizable to the K-card trick. The assistant has 5 ways to choose which card to hide and 24 ways to arrange the remaining four cards, so they only have 120 actions in any given situation. Ergo, the magician should only be able to extract 120 alternatives’ worth of information from knowing what action the assistant would take.

This is a bit fishy, because of course even with N > 120, the trick could happen to work sometimes. That is, if the magician tells the assistant the strategy by which they will guess the missing card, the assistant may, for some sets of 5 cards drawn even from a large deck, manage to show an arrangement of four that will lead the magician to guess correctly.

The crux of formalizing the argument is to move to the global view, but we can do that without additional computations. Consider the space of all states reachable by any strategy of the assistant. In our case, this is equivalent to ordered sequences of five cards, with the last face down. There are obviously (N-4)M of these, where M is the number of states the magician observes (four-card sequences, in our case), however many of those there are. When the assistant and the magician choose a strategy for the assistant, they make most of these impossible. Indeed, since the assistant always has exactly 120 options, after they have chosen one to take in each situation, we have exactly (N-4)M/120 states that remain possible with that strategy. For the trick to always work, this last expression must be no more than M; M cancels, saving us the trouble of computing it, and we are left with N-4 ≤ 120 as desired.

By the way, one of the authors of this essay, Tanya Khovanova, taught this trick to her PRIMES STEP students, who were students in grades 7 through 9. They found and studied interesting generalizations of this trick and wrote the paper Card Tricks and Information available at the arXiv. They studied many variations of the trick, including the ones where the assistant is allowed to put the cards face down. This interesting variation is outside the scope of this essay.

We would like to use as an example one of the tricks described in the paper: the K-card trick, where the assistant hides one card and arranges the rest in a circle. The implication is that when the audience member describes the arrangement to the magician, they describe the circle clockwise in any order. Our argument works here as follows. We count the number of the assistant’s actions: K ways to choose the hidden card and (K-2)! ways to arrange the cards in different circles up to rotation. Thus, the number of different actions is K(K-2)!. Hence, the deck size doesn’t exceed K(K-2)! + K – 1, as we can exclude the K-1 cards in the circle, as they aren’t hidden. Not surprisingly, this is the same formula as in the paper.