Number Sequences And Pigeonhole

Let's play a game. The task is to recognize a permutations of the numbers 1 through 10. Some numbers are hidden, others (at most 6 of them) are clearly shown. Sometimes the numbers appear in blue, sometimes in red. With such preliminaries, can you now name the hidden numbers? (For a training session we can use 5 numbers, of which at most 2 are shown.)

Believe me you can, for I shall presently reveal the secret of my selection. It follows from Dirichlet's box principle, that in any permutation of 10 distinct numbers there exists an increasing subsequence of at least 4 numbers or a decreasing subsequence of at least 4 numbers. (A general statement is due to P. Erdös and G. Szekeres, see [Aigner], p. 124.) These are the numbers that remain hidden. You'll know that the sequence is increasing if the numbers are red. It's decreasing if they are blue. (Note that the same problem is illustrated with a different applet.)

References

1. M. Aigner, G. Ziegler, Proofs from THE BOOK, Springer, 2000 2000
2. M. Gardner, The Last Recreation, Copernicus, 1997

Copyright © 1996-2008 Alexander Bogomolny