Generalizing Fitch Cheney’s Five-Card Trick

Ok, this should be the last of the card magic for a while.  But there is actually some relevance to recent discussion, as we will see; I was reminded of this trick by the prisoner puzzle from the last couple of posts.  I will describe the effect, including a “computer version” that makes for an interesting classroom exercise, and finally present a generalization of some mathematical results about how the trick works.

First, the original effect, as credited to William Fitch Cheney, Jr.  The magician turns his back (or leaves the room), and asks a spectator to look through a standard 52-card poker deck and select any 5 cards.  For example:

Cards selected by the spectator.

The magician’s assistant takes the chosen cards, then hands four of them, one at a time, back to the spectator who announces each card in turn to the magician, until one card remains, known only to the spectator and the assistant:

Cards presented to the magician.

After hearing the four cards, the magician immediately announces the fifth chosen card, the ace of diamonds!

It is an interesting problem to determine how the trick is done.  The relationship to last week’s prisoner puzzle is clearly seen: in both cases, we are presented with an arbitrarily selected configuration of objects, and we must communicate some information about that configuration by modifying it in some limited way.

The trick obviously requires two parties, both of whom know how it works: the assistant to select and order the subset of 4 cards, and the magician to determine the remaining card.  However, we can replace either or both of the assistant and the magician with a computer, which can be convenient for experimenting with the trick repeatedly, particularly in the classroom where students can search for patterns in the way cards are selected and ordered.  In fact, performing the trick does not even require an actual deck of cards; the spectators/students can simply name their chosen cards.

To that end, following are two (deliberately comment-free) Python scripts that substitute for the assistant and the magician:

The assistant:

import itertools

ranks = ['ace', 'two', 'three', 'four', 'five', 'six', 'seven', 'eight', 'nine',
         'ten', 'jack', 'queen', 'king']
suits = ['clubs', 'diamonds', 'hearts', 'spades']

print("I am the magician's assistant.  Please select any five cards from a")
print("standard deck, e.g., 'ace of clubs', 'two of diamonds', etc.")

cards = []
for i in range(5):
    while True:
        try:
            card = input('Enter card {0}: '.format(i + 1))
            card = card.lower().split()
            cards.append((ranks.index(card[0]), suits.index(card[-1])))
            break
        except (IndexError, ValueError):
            print('Invalid card, please try again.')

for (i, j) in itertools.combinations(range(5), 2):
    if cards[i][1] == cards[j][1]:
        offset = (cards[j][0] - cards[i][0]) % 13
        if offset > 6:
            (i, j) = (j, i)
            offset = 13 - offset
        order = [cards[k] for k in (set(range(5)) - set((i, j)))]
        order.sort()
        order = list(list(itertools.permutations(order))[offset - 1])
        order.insert(2, cards[i])
        break
    
print('Read the following cards in order to the magician:')
for (rank, suit) in order:
    print('The {0} of {1}.'.format(ranks[rank], suits[suit]))

The magician:

import itertools

ranks = ['ace', 'two', 'three', 'four', 'five', 'six', 'seven', 'eight', 'nine',
         'ten', 'jack', 'queen', 'king']
suits = ['clubs', 'diamonds', 'hearts', 'spades']

print("I am the magician.  Please tell me four of the cards that you selected")
print("in order as given to you by my assistant.")

cards = []
for i in range(4):
    while True:
        try:
            card = input('Enter card {0}: '.format(i + 1))
            card = card.lower().split()
            cards.append((ranks.index(card[0]), suits.index(card[-1])))
            break
        except (IndexError, ValueError):
            print('Invalid card, please try again.')

rank, suit = cards[2]
order = (cards[0], cards[1], cards[3])
offset = list(itertools.permutations(sorted(order))).index(order) + 1
rank = (rank + offset) % 13

print('The remaining card is the {0} of {1}!'.format(ranks[rank], suits[suit]))

There is a lot of interesting mathematics in this trick.  See the references below for two great detailed discussions; Simonson and Holm in particular describe the trick as a tool for student investigation of the many involved areas of discrete mathematics.

One question that has been addressed frequently is, with how large a deck of cards may the trick be performed?  It turns out that 52 cards is nowhere near the limit; the trick is possible even with a deck of 124 cards.  More generally, the papers below show that, given any m-subset of n cards, it is possible to determine the remaining card from an appropriate arrangement of of them, if and only if .

The main point of this post is to generalize this further.  It is often the case in mathematics that a problem may be easier to tackle– or at least more elegant– if we try to solve a slightly harder problem instead.  I think this is one of those cases.  Consider the following more general form of the trick: for a triple , with , given any m-subset of n cards, arrange k of them so that the remaining cards may be determined.  Thus, for example, Fitch’s original trick corresponds to the triple (52, 5, 4).  Then we will show that the trick is possible if and only if

where the left-hand side is the binomial coefficient and the right-hand side is the falling factorial.  More simply, the number of subsets of m cards must be at most the number of arrangements of k cards.

Proof: That the condition is necessary is straightforward, since each possible subset of m cards chosen by the spectator must be “communicated” to the magician by a distinct k-arrangement.  To show TONCAS (the obvious necessary condition is also sufficient– I was a student of West:)), consider the bipartite graph G with partite sets S and T, where S is the set of all m-subsets of n cards, and T is the set of all k-arrangements, with edges defined by inclusion.  A matching saturating S would correspond to a strategy for performing the trick.

The König-Egerváry theorem states that the maximum size of a matching in a bipartite graph equals the minimum size of a vertex cover.  A simple corollary guarantees a matching of size at least , since each vertex in a cover is incident to at most edges.  Assuming — the condition in the theorem– this ratio is , thus G has a matching saturating S.

To wrap up, note that the theorem proved in the references corresponds to the particular case , in which case the graph G for the bounding condition is regular and .  Here we are simply making use of the more general version of Hall’s marriage theorem mentioned by Simonson-Holm… or the Birkhoff–von Neumann theorem for doubly-stochastic matrices used by Kleber, or the König-Egerváry theorem, or Menger’s theorem about graph connectivity, or the Ford-Fulkerson theorem about network flows, or Dilworth’s theorem about partially ordered sets… all of which are equivalent!

References:

1. Kleber, M., The Best Card Trick. Mathematical Intelligencer, 24 (2002). [PDF]
2. Simonson, S. and Holm, T., Using a Card Trick to Teach Discrete Mathematics. Primus: Problems, Resources and Issues in Mathematics Undergraduate Studies, 13 (2003):248-269. [PDF]