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 m-1 of them, if and only if n \leq m! + m - 1.

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 (n, m, k), with n > m > k, given any m-subset of n cards, arrange k of them so that the remaining m-k 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

{n \choose m} \leq (n)_k

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 e(G)/\Delta(G), since each vertex in a cover is incident to at most \Delta(G) edges.  Assuming |S| \leq |T|— the condition in the theorem– this ratio is |S|, thus G has a matching saturating S.

To wrap up, note that the theorem proved in the references corresponds to the particular case k = m - 1, in which case the graph G for the bounding condition is regular and |S| = |T|.  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]

Prisoner Puzzles

Before discussing the solution to last week’s problem, I want to mention another interesting problem, which led to this latest one:

100 Prisoners. This is perhaps my favorite of the many of the “prisoners-with-a-strategy-for-collective-survival” type.  It goes as follows: you and 99 others are held prisoner by the usual bloodthirsty yet eccentric pirates, who offer the following scenario.  In a room are 100 boxes, and in each box is a slip of paper with exactly one prisoner’s name on it.  Each prisoner’s name appears on the slip in exactly one box.  Each of you in turn will be taken into the room, one at a time, and allowed to open at most 50 boxes, inspecting the slip in each box, looking for the slip with your own name on it.  You must leave the room and the boxes exactly as you found them, and you may not communicate with the other prisoners in any way.  Once all 100 prisoners have entered and exited the room, if all 100 of you were able to find your name, then you will all be freed.  If even one of you fails to find his name, you will all be executed.  You may discuss strategy before beginning.  How can you maximize your chance of survival?

This problem is interesting because, at first glance, survival seems nearly impossible.  For example, if each prisoner simply chooses any 50 boxes at random, finding his own name with probability 1/2, then the probability that all of the prisoners find their names is only (1/2)^{100}.  The surprising fact is that it is possible to do much better, using a clever and rather simple strategy.

I have seen this problem, and its solution, before– what is recently new to me is that this simple strategy is in fact best possible, proved in 2006 by Eugene Curtin and Max Warshauer; see “The Locker Problem” for their excellent article describing the problem, the strategy, and its optimality.

Two Prisoners. While reading about Curtin and Washauer’s result, I stumbled upon the problem in last week’s post, originally discussed on Oliver Nash’s blog.  There is a great description there not only of the solution, but also of some interesting generalizations to other similar problems.  But the strategy may be described very concisely:

Number the squares on the board from 0 to 63.  You compute the bitwise exclusive-OR of (1) the indices of all of the squares with coins showing heads, together with (2) the index of the square selected by the pirate.  Flip the coin on the square with the resulting computed index.  Your friend computes the bitwise exclusive-OR of the indices of squares showing heads; the resulting index indicates the selected square.

The chess board turns out to be a bit of a red herring.  That is, consider trying to solve the problem for a different number of squares/coins n than 64.  It is not necessary that n be a perfect square.  A nice application of the pigeonhole principle shows that a necessary condition is that n be a power of 2 (why?).  The above explicit strategy shows that this condition is also sufficient.

A Prisoner Puzzle

This week I want to share what I thought was a very clever puzzle.  I stumbled upon this via the usual roundabout path, while investigating some new results I had learned about a couple of other problems.  This puzzle turns out to be related to those other problems in some interesting ways.  I will discuss those relationships next week… along with attribution for this puzzle in its original form, since I modified it a bit here to include pirates:

You and a friend are being held prisoner by pirates.  The pirates are bloodthirsty, and so are threatening your execution.  However, they are also eccentric, and so are offering freedom for both of you if you can solve the following puzzle.

First, one of the pirates will take you into a room, leaving your friend outside.  In the room is an 8×8 chess board and 64 identical doubloons.  The pirate will place exactly one doubloon on each square of the board, showing either heads or tails as he sees fit (e.g., randomly).  He will then select and point out to you one square on the board.  You must then turn over exactly one of any of the doubloons (i.e., turning heads to tails, or tails to heads), and exit the room.

At that point, the pirate will take your friend into the room, leaving you outside.  If your friend is able to identify the square that was selected by the pirate, then both of you will be set free.  Otherwise, you will both be forced to walk the plank.

The pirates have explained these rules to you beforehand, and have allowed you and your friend to discuss strategy before beginning.  What strategy should you use to maximize your chance of survival?

CAPTCHAs revisited

This past week I spent some time experimenting with hacking the CAPTCHAs at the login page for one of my online financial institutions.  (See here for a discussion almost a year ago about reCAPTCHAs, a particularly interesting additional application of CAPTCHAs.)

I was motivated to do this because (1) it seemed like an interesting problem, since I don’t know much about image processing or OCR; and because (2) these particular CAPTCHAs seemed disturbingly simple… in more than one way, as we shall see.

Actually, I will skip over the image processing rather quickly.  Although that was my initial interest in the problem, it is not really my focus here.  The important observation is simply that it was easy.  The CAPTCHA images are always the same size in pixels, they are always four capital letters, the letters are never stretched or skewed, and they always make up an English word.  The only real challenge is the image background, which is a combination of a varying “bumpy” texture and some skewed cross-hatch lines through the letters.

Parsing the CAPTCHAs took just a few steps.  First, color-quantize the image first down to eight colors, then down to two (filtering on one of the eight) to get a black and white image.  This almost completely removes the texture and cross-hatching, leaving just the letters.  Then apply a couple of 3×3 box filters, the first to remove any “island” dots in the image left over from the background removal, and the second to smooth out any “toothiness” in the edges of the characters.  Finally, I didn’t even have to bother with my own OCR.  The open-source GOCR software did the job just fine.

The result is about 20 lines of Mathematica code, yielding an automated solution with a success rate of approximately 90%.  (This is based on my manual sample of logins over the course of several days, since I don’t want to actually throw a bot at the site.)

But even more interesting than the CAPTCHA images themselves is the protocol, or manner in which the CAPTCHAs are incorporated into the login process.  Once a user reaches the page with the CAPTCHA– after entering a valid account password– a notice at the bottom of the page informs the user that he or she can refresh the page with a new CAPTCHA if the current one is too difficult to read.  I had not really noticed or tried this “feature” before, but it turns out that refreshing the CAPTCHA does indeed load a new image… but the four-letter word does not change.

What does this mean for an automated attempt at solving the CAPTCHA?  Recall the 90% success rate mentioned previously; in most of the 10% of cases where my algorithm fails, the problem has not been that it comes up with the wrong four-letter word.  Instead, it knows that it failed, since one or more of the letters were unrecognizable.  In those cases, subsequent refreshes of the CAPTCHA have eventually yielded a successful solution.

So what is the point of all of this?  I think the important questions to ask are, “What type of attack are we trying to prevent?” and “What reduction in probability of successful attack does this additional complexity of protocol provide?”  The moral here seems to be that increased complexity (“let’s add CAPTCHAs to protect against bots”) does not imply increased security… and that increasing convenience (“but we’ll let users refresh the image if the text is too hard to read”) almost always decreases security.