Card Colm

June 2005
Ironically, Uncle Paul, as he was known to many, apparently never displayed any interest in mathematical magic in his lifetime, but this uniquely productive and extraordinarily influencial world wide wanderer — surely the most notable 20th century manifestation of the mathematical web — can be relied upon to assist in a little mathematical fun and games from beyond the grave. (For an earlier discussion covering some similar ground see this October 2000 AMS Online link.)
Let us first reacquaint ourselves with mathemagicans Aodh and Bea, the heros of our February musings. A volunteer selects some shuffled cards. Aodh glances at them, and then communicates (purely mathematically) partial information to Bea, basically by displaying only some of the cards. Bea, who had witnessed nothing prior to this display, reveals the identity of the hidden cards. In February, we looked at a family of tricks in which Aodh was handed 4 or 5 cards, and showed Bea all but one of them, some (or even all!) being facedown, prompting Bea to identify the final hidden card. This time around, Aodh will show Bea just 2 of 5 selected cards, and expect Bea to identify all 3 of the remaining ones.
What's the secret? Is Bea obtaining the required information telepathically from Gyorgy Szekeres, now retired in Australia? Not quite...
This is a mix of mathematics and magic: we must confess that the 5 cards used are not at all random, but are planted on the top of the deck at the outset, and then retained there through assorted shuffles. The identity of these 5 cards is known to Aodh and Bea all along. But that still leaves some questions: (1) Isn't any of the 5! = 120 possibly orderings of these cards possibly in the display, since the volunteer mixed these cards thoroughly? (2) Is Aodh's showing just 2 cards to Bea sufficient for her to determine in which of the 3! = 6 possible arrangements the other 3 cards are? As we shall see, the answers to these questions are Yes and No, respectively!
Let's consider a simple version of the trick which is too transparent to actually perform, but which illustrates the principle nicely. Suppose that the top cards of the deck at the outset are the Ace, 2, 3, 4 and 5 of any one suit. When the volunteer lays them out faceup on the table, having mixed them randomly, what everybody sees is some jumble (permutation) A B C D E of {Ace, 2, 3, 4, 5}.
What Aodh does now is scan quickly, from left to right, seeking a rising subsequence of length 3. E.g., if the cards are ordered 2, Ace, 4, 5, 3, then Aodh could opt for 2, 4, 5 (or Ace, 4, 5) as the desired subsequence. That leaves Ace & 3 (or 2 & 3 if the other subsequence is desired — either choice is fine) "out in the cold." The volunteer now turns all of the cards facedown, and Bea joins the group. Aodh can now turn over — and hence reveal — the cards Ace & 3, in that order. Bea knows, of course, which cards are missing, and will assume that they are in that order, leading to her being able to conclude the trick successfully. The volunteer may ask for the cards to be identified in any order desired.
But what, you may well ask, if there is no rising subsequence of length 3? You may be thinking:
In each list of five there is bound, To be three that do rise; is that sound? In a paper by Erdös, With Gyorgy Szekeres, A counterexample is found. 
The paper referred to above really exists, and goes (much) further. It certainly guarantees that:
In any sequence of 5 ordered objects, there is a monotone subsequence of length 3; in other words there is either a rising subsequence of length 3, or failing that a falling subsequence of length 3.
For instance, if the cards are laid out in the order Ace, 4, 5, 3, 2, then 4, 3, 2 (or if preferred, 5, 3, 2) is a falling sequence of length 3. In this case, Aodh turns the other two cards faceup, in reverse order — i.e., from right to left. So what Bea really has to watch out for is in what order Aodh reveals the 2 cards that are turned over; that's the key to knowing what order the other 3 cards are in.
Here is an elementary proof of the above claim: suppose we have 5 different numbers listed in the order A B C D E. Without loss of generality we may assume that A < B. We claim that if there isn't a rising subsequence (from left to right) of length 3, among these 5 numbers, then there is a falling one instead. Assume there is no such rising subsequence. We must have each of C, D, and E less than B, as otherwise we'd have a rising subsequence of length 3 starting with A B. If it happens that C > D, then B C D is a falling subsequence of length 3, whereas if D > E, then B D E is a falling subsequence of length 3; in either case we are done. But one of those subcases must in fact occur, for otherwise we'd have both C < D and D < E, and hence a rising subsequence C D E of length 3, contrary to our assumption.
Why those cards, and in that order? Fan out these actual cards, picked out of a real deck, from left to right, and look at the lower right hand corners: with a little imagination, you may notice that the upsidedown 3, J, 4, Q, 5 resemble a version of the word "Erdös". As long Aodh and Bea both remember these particular cards in order, all is well. (Notice the black pythagorean triple, separated by the two red members of royalty, representing Erdös and his beloved mother!)
Suppose that the volunteer lays out the cards in the order Q, 3, 4, J, 5, from left to right. Since 3, J, 5, form a rising subsequence, these are the ones which Bea will identify, so that after all of the cards are turned facedown, and Bea joins the proceedings, Aodh turns over the Q and 4, in that order, to reveal:
Bea knows that the 3, J and 5 are missing, and that they are in that order.
If you wish to be able to repeat the trick right away, you need to have loaded the deck with 10 prearranged cards on top at the outset: perhaps the above 5 followed by 5 others whose values are easy to recall, such 6, Ace, 7, K, 10 — Palkó was the name Erdös's mother used when addressing her son — or 3, Ace, 4, Ace, 6 — think of π to 4 decimal places. You may need to vary the suit cycling.
This, as Gardner points out, is a special case of an Erdös and Szekeres result from 1935, one form of which says that provided k is the smallest positive integer whose square is at least n, then in any list of n distinct numbers, there will always be at least k that will either be in rising or in falling order. The card trick considered above is the case k = 3 and n = 5, where we provided a proof that it really works. Gardner's ten soldiers example — which can also be turned into a card trick — is the case k = 4 and n = 10.
The result is really about totally ordered sets, which means that identical card values pose no problem provided that we have in mind a total ordering on the set of cards being considered. A proof of the general Erdös & Szekeres result, which uses the pigeon hole principle, can be found in Martin Aigner & Gunter M. Ziegler's Proofs from The Book (Springer, 1998).
In one sense, identifying 3 out of 5 cards is more impressive than identifying 4 out of 10, but there is one advantage to working with 10 cards rather than 5: it's not at all unusual to find a rising (or falling) subsequence of length 5 or longer. In such cases there will be sufficient (all Aodh needs is 2!) other cards to turn over — either left to right, or right to left — to communicate to Bea the sense of the longer hidden subsquence, of length up to 8. The varying subsequence length possibility also adds an air of mystery should the trick be repeated. It's also possible to have rising and falling subsequences of length 4 (or even 5) — indeed the sum of the lengths can be as much as 11 — so Aodh should always check for both before proceeding, and make use of the longest such.
Of course, in the original five card trick, Aodh may find a monotone subsequence of length 4 or 5, but such cases can only be exploited half of the time: e.g., by means of a prior arrangement with Bea that if fewer than 2 cards are turned over, those remaining can safely be assumed to be rising.
Colm Mulcahy (colm@spelman.edu) has taught at Spelman College since 1988. He is currently the chair of the department of mathematics there. Here is a hint for any readers who may still be wondering how to manage the mathemagicians' names: it's as easy as "Aodh, Bea," see? More of Colm's writing on mathematical card tricks can be found at http://www5.spelman.edu/~colm/cards.html.