This card trick (see [2]) was discussed in a session of the ETH Math Youth Academy, illustrating the Pigeonhole principle. It is based on the case n = 3 of the following theorem of Erdos and Szekeres (see, for example, [1], p. 162):
Theorem 1. Any sequence of n2 +1 pairwise distinct real numbers contains a
monotonic subsequence of length n + 1. Proof. Consider a sequence a1, ..., an2+1 of pairwise distinct real numbers. For each i = 1, ..., n2 + 1; denote respectively by xi and yi the lengths of the largest increasing and decreasing subsequences beginning at ai. We claim that (xi, yi) ≠ (xj, yj) for i ≠ j. Indeed, say i < j. If ai < aj, then xi > xj, since one can add ai to an increasing subsequence of length xj beginning at aj. Similarly, yi > yj if ai > aj.
If we assume that xi, yi ≤ n for all i = 1, ..., n2 + 1; then there would be only n2 possibilities for each pair (xi, yi): However, we have n2 + 1 pairwise distinct such pairs, contradicting the Pigeonhole principle.
First, the magician and the assistant agree on an ordering of the 10 cards. The assistant finds a monotonic subsequence of 4 cards and simply turns up the other 6 cards (going left–right or right–left depending on whether the chosen monotonic subsequence is increasing or decreasing). The magician now knows what the 4 face–down cards are as a collection and how they are ordered, so he can easily identify each one of them.
References:
[1] M. Aigner, G. Ziegler, Proofs from the Book, Springer, 1998.
[2] B. Epstein, All you need is cards, in Puzzler’s Tribute, D. Wolfe, T. Rodgers (eds), A K Peters, 2002.
