# A Little Erdös/Szekeres Magic

June 2005

A classic result in real analysis asserts that every infinite sequence has a infinite monotone (i.e., rising or falling) subsequence. A finite version of this, associated with the Hungarian mathematicians Paul Erdös (1913-1996) and Gyorgy Szekeres (born 1911), can be adapted to yield a two-person prediction trick, which we explore below in terms of cards.

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 face-down, 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.

## A Sequential Con

Here's the basic Erdös/Szekeres (inspired) trick: Aodh shuffles the deck, then peels off the top 5 cards and gives them to a volunteer for additional mixing. Aodh then has the volunteer lay out the cards in a face-up row on the table, stressing how totally random everything is. Next, Aodh has the cards turned face-down. Finally, Bea is invited into the room, for the first time, to view the displayed cards. Aodh silently turns over 2 cards, and invokes the spirit of the late great Paul Erdös. Bea picks up the vibes, and unhesitatingly identifies the 3 remaining face-down cards correctly, in any order desired.

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 face-up 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 face-down, 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 face-up, 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.

## The Erdös Five Card Trick

Of course, most audiences will suspect something if the trick is performed as suggested above, using an Ace, 2, 3, 4, 5 of the same suit. To throw people off the scent, one could use another ordering of the cards employed, such as alphabetical, i.e., Ace, 5, 4, 3, 2, although that's not so helpful with these particular cards. Here's a better idea: use any 5 cards in an order that you can easily remember. For instance, we could start with the following "Erdös numbers" (while ditching the same old suit concept): 3♣, J, 4♠, Q, and 5♣ at the top of the deck, the suits cycling in the usual CHaSeD order.

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 face-down, 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 pre-arranged 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.

## Military Two-Step Inspiration

The above card trick and limerick were inspired by a remark of Martin Gardner's in his Riddles of the Sphinx and Other Mathematical Puzzle Tales (MAA, 1987) to the effect that: in any "a row of 10 soldiers, no two of the same height... no matter what the order, there will always be at least 4 among the ten, not necessarily standing next to each other, who will be in ascending or in descending order."

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).

## Is Bigger Better?

The Gardner/Erdos/Szekeres inspired trick can also be done with 10 not-so-random cards being given to the volunteer, to jumble and lay out in a face-up row. The cards are then turned face-down, and Aodh turns 6 face-up again for Bea, who correctly identifies the other 4. Here the alphabetical ordering Ace, 8, 5, 4, 9, 7, 6, 10 3, 2 (within one suit) works well, if Aodh and Bea are up-front about the fact that they both know what all 10 cards are, or they could be ambitious and use 10 "random" cards which both mathemagicians memorize. North American phone numbers, with area codes, can be used, modulo some pre-agreed suit conventions.

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.