Increasing or decreasing subsequence

Given any sequence of mn+1 real numbers, some subsequence of (m+1) numbers is increasing or some subsequence of (n+1) numbers is decreasing.

Solution


|Contact| |Front page| |Contents| |Up|

Copyright © 1966-2016 Alexander Bogomolny

Given any sequence of mn+1 real numbers, some subsequence of (m+1) numbers is increasing or some subsequence of (n+1) numbers is decreasing.

Assume that the result is false. For each number x in the sequence, form the ordered pair (i, j), where i is the length of the longest increasing subsequence beginning with x, and j is the length of the longest decreasing subsequence ending with x. Then, since the result is false, 1 ≤ i ≤ m and 1 ≤ j ≤ n. Thus we have mn + 1 ordered pairs, of which at most mn are distinct. Hence two members of the sequence, say a and b, are associated with the same ordered pair (s, t). Without loss of generality we may assume that a precedes b in the sequence.

If a < b, then a, together with the longest increasing subsequence beginning with b, is an increasing subsequence of length (s + 1), contradicting the fact that s is the length of the longest increasing subsequence beginning with a. Hence a ≥ b. But then, b, together with the longest decreasing subsequence ending with a, is a subsequence of length (t + 1), contradicting that the longest decreasing subsequence ending with b is of length t. There is no way out; our assumption is false, and the result is therefore true.

(There is an interactive illustration of the above result and another one, perhaps a little more entertaining. According to Erickson, the problem is now known as the Erdös-Szekeres theorem.

References

  1. M. Aigner, G. Ziegler, Proofs from THE BOOK, Springer, 2000
  2. A. Engel, Problem-Solving Strategies, Springer Verlag, 1998, p. 61
  3. M. Erickson, Beautiful Mathematics, MAA, 2011
  4. M. Gardner, The Last Recreations, Copernicus, 1997

Related material
Read more...

  • Sum of Integers
  • More than half of the integers from {1, 2, ..., 2n}
  • Consequences of Getting More Than a Half
  • Remainder Multiples of 1997
  • Intersecting Subsets
  • Over-The-Counter Pigeonhole
  • Women in a theatre: Pigeonhole Principle
  • Pigeonhole Among Friends
  • Not Exceeding 24

  • |Contact| |Front page| |Contents| |Up|

    Copyright © 1966-2016 Alexander Bogomolny

     62687313

    Search by google: