Wednesday, November 9, 2011

The Best Card Trick

... is the title of an article [PDF] from the Mathematical Intelligencer I recently came across that, well, discusses a namesake card trick. As  it turned out, the somewhat presumptuous title notwithstanding, the trick happens to be pretty interesting. Not to mention it gives me enough material to to gab about and break out of my posting hiatus (before slipping into another :) ). So, here we go ...

A bit of history

The original article offers close to 1.5 pages of history if you are interested - consider this section a "tl;dr"-ed version.

  • The trick appeared in the book Math Miracles by Wallace Lee, where it is credited to William Fitch Cheney Jr., a.k.a. "Fitch".
  • The article is by Michael Kleber.

Here's where I would have ideally ended this section (a bit of history: check) but Fitch having been the interesting character that he had been, it would be unfair if I didn't mention the following facts about him before we move on:

  1. If a name like "Fitch" inspires the image  of an ordinary performer of card tricks, or worse still, a street magician, you couldn't be more wrong - Fitch was awarded the first PhD in mathematics from MIT in 1927.

  2. As a teacher, Fitch seems to have been unusually entertaining:

  3. "... he enjoyed introducing magic effects into the classroom, both to illustrate points and to assure his students' attentiveness. He also trained himself to be ambidextrous (although naturally left-handed), and amazed his classes with his ability to write equations simultaneously with both hands, meeting in the center at the "equals" sign."
      --- from a description of Fitch by his son, Bill Cheney

Trick, and a mathematical treat

To appreciate how the trick works under the hood, lets start by looking at it from the point of view of the audience. If you were at the receiving end of the trick this is what you would see:

(1) The magician holds out a normal deck of 52 cards to you, and asks you to pick 5 cards.

(2) You do so and hand them over to his assistant.

Say, this is what you pick:

(3) Of the 5 cards handed over to her, she hands 4 of them to the magician. Say, these:

(4) He looks at the 4 cards handed to him, and with < insert favorite dramatic gesture here > announces the 5th card you had selected.

Take a while to think about what happened here. Assuming a normal, well-shuffled deck and no underhand techniques, the objective of the magician seems to be to look at 4 cards, handed to him by his assistant, and infer the 5th. With absolutely no prior knowledge of the selection on part of the magician (in other tricks this is typically arranged for by using a deck with more cards of one kind than another, or stacking it up in some particular way etc), how exactly is the assistant to indicate the rank and suit of the 5th card using the 4 cards she hands over?

What messages can you pass with 4 cards ?

A possible way seems to be arranging 4 cards in a way that identifies the 5th card i.e. you could use the ordering of 4 cards to encode the suit and rank of the 5th card.

But there is a catch here - 4 cards can be arranged in 4! = 24 different ways, whereas the 5th card could be any one of the remaining 52 - 4 = 48 cards. Apparently we do not have enough arrangements of 4 cards to indicate the 5th card. One card more, and we would have been good to go - but, the technique doesn't seem workable as-is.

In essence, the trick is not a sleight-of-hand-ish trick - it boils down to compressing and conveying information. Fitch being a mathematician probably has something to do with this.

So,which 4 cards does the assistant hand over to the magician? And how do these indicate the 5th card?

The workings

We saw how we fall short when we try to use orderings for our purpose; this is where the trick gets interesting. Instead of abandoning the approach completely, it looks deeper at the kind of objects we are dealing with. Each card is marked with a suit and a rank - can these attributes help us in squeezing in more information? Apparently, yes:
  1. Since there are just 4 suits, but you have picked 5 cards, there are at least 2 cards of the same suit in your selection (Hello, pigeonhole principle!). In the above example these are 3 ♠ and 10 ♠ . As per a convention decided upon by the assistant and the magician, the assistant holds back one of the cards with a repeated suit, and in the arrangement of cards he hands to the magician, he positions the other card of the suit as the first card. Looking at the first card, the magician now only needs to guess the rank of the unseen card - the suit is same as that of the first one.

    Look at the cards in step 3 above; 10 ♠ is the first card handed over. The magician knows that the 5th card is also a spade.

    But with the first card used to reveal just the suit, we have only 3 cards left to guess the rank of the 5th card. Which can take on 13 values. But 3 cards can be arranged in only 3! = 6 ways.

    Ouch. Again.

  2. Since our strategy is already piggybacking on the repeating of suits, it's worth asking, among the cards with the repeated suit, is there a good way to pick the card the assistant would be sliding into the first position?

    In the above example, this is equivalent to asking, between 3 ♠ and 10 ♠, which card should be put in the first position?

    Is there an optimal choice here? Optimal in a way that helps us to work around he limitation we encountered above i.e. can choosing the 1st card wisely, lets us use just 3 cards to indicate the rank of the 5th card ?

    Turns out, the answer is yes. Here's a short, math-savvy hint: modular arithmetic.

    In simple words, here, this means that we do not directly indicate the rank of the 5th card, but we indicate what number you should add to the rank of the 1st card to obtain the rank of the 5th card. Except that we agree to a way of handling the addition when it goes beyond 13 - in such cases, we simply start counting at 1 again.

    This can be easily understood by imagining the ranks to be laid out in a circle. Adding x to a number y here is equivalent to going x steps around the circle, clockwise, starting from y.

    So, 10+5 is 2. 13 + 1 is 1. And, of course, 2 + 3 is 5.

    How does this help in working around our earlier limitation? Consider the shorter distance between any 2 points on the circle - its
    never greater than 5. This means that of 2 points in this circle, I could always pick a point, so that you wouldn't need to add a number more than 6 to reach the other point. This is important since the remaining 3 cards - the ones at positions 2nd, 3rd and 4th - can be arranged in 6 different ways.
    Take the points 3 and 10 for example (the ranks of our cards with the suit ♠ ). If you were given 3, you would need to add 7 to get to the point 10. But if you were given the point 10, you would need to add 6 to get to the point 3. This is why the assistant passes 10 ♠ to the magician in our example, and not 3 ♠ (and arranges the other cards to indicate the number - 6 - to be added; we'll get to the arrangement in a while)
    Thus, it turns out that if we pick right the card of the repeated suit to be given to the magician, the ordering of 3 cards is sufficient to indicate the rank of the unseen card. This completes our strategy.

Here, to implement point 2, one could follow any system to encode numbers by orderings, as long as the magician and his assistant have agreed upon it. A simple way could be to use the ordering of suits and ranks used in the game of bridge:
  1. Ordering of suits, highest to lowest: ♠, ♥, ♦, ♣

  2. Within a suit, ordering of ranks, highest to lowest: Ace (A), King (K), Queen (Q), Joker (J), 10, 9, 8, 7, 6, 5, 4, 3, 2.
For our cards in positions 2nd to 4th ( 8 ♥, K ♦, A ♣), this implies the following encoding for all possible arrangements (assuming a "lower" ordering corresponds to a lower number):

  • A ♣, K ♦, 8 ♥ → 1

  • A ♣, 8 ♥, K ♦ → 2

  • K ♦, A ♣, 8 ♥ → 3

  • K ♦, 8 ♥, A ♣ → 4

  • 8 ♥, A ♣, K ♦ → 5

  • 8 ♥, K ♦, A ♣ → 6
Thus, looking at the ordering of these 3 cards, our magician adds "6" to the rank of the first card, which is 10. This tells him that the 5th card has a rank 3 (remember he already knows that the suit is a ♠).

In summary

The following image tries to sum up the reasoning of the magician:

You can blame Google for the crummy resizing.

Stage advice ...

Some practical advice from the article if you are indeed planning on performing the trick:

  1. If trying to determine what number the ordering of the 2nd, 3rd and 4th cards corresponds to in the manner discussed, seems a little clumsy, the author of the article suggests his own variation.

    "... place the smallest card in the left/middle/right position to encode 12/34/56 respectively, placing medium before or after large to indicate the first or second number in each pair"

    As an example, the ordering "A ♣, 8 ♥, K ♦" would imply a rank of 2, since the smallest card, A ♣, is in the first position (so this is either rank 1 or 2) and the medium card, K ♦, follows the large card, 8 ♥ (which makes it rank 2).

  2. This one, straight from Fitch. If you are repeating the trick to an audience, say for more than a few times, there is the risk that someone would notice that one of the cards with a repeated suit is always in the first position. In such a case, place the card that indicates the suit in the (i mod 4)th position for the ith performance (we assume position "0" indicates the 4th position).

    Thus, for the 1st performance this card is in position 1, for the 2nd performance this is in position 2, for the 7th performance, assuming your audience is still around and awake, this goes in at position 3 (since, 7 mod 4 = 3).

If you go through the various steps above, the ideas involved seem to just about fit in: simple ordering seems deficient? - repeated suit to the rescue; 3 cards are insufficient to indicate a rank? - modular arithmetic alert.

happy-go-lucky patchwork of clever ideas as it were...

... which, well, really is fair game. However, the key contribution of the article is that it convinces you this is not all that there is to it: it analyzes these seemingly ad-hoc steps rigorously and suggests extensions of the trick. Unfortunately, this is not something I will go into, in this post, since I want to keep it fairly non-technical. For those who are interested, going through the original article is strongly recommended. I intend to follow-up this post with another one focused only on the generalizations, at a later point in time.