Posers and Puzzles

Posers and Puzzles

  1. Standard memberChronicLeaky
    Don't Fear Me
    Reaping
    Joined
    28 Feb '07
    Moves
    655
    01 Mar '08 05:13
    If you pick an integer N, I will form a sequence consisting of N^2 + 1 real numbers (or integers, or points on an oriented line, or any other subset of a totally ordered set). If I don't tell you what sequence I've chosen, how many elements are in the largest increasing or decreasing subssequence of my sequence whose existence you can guarantee?
  2. Joined
    30 Oct '04
    Moves
    7797
    01 Mar '08 08:32
    n+1 if I recall correctly. There is an Erdos-Szekeres Theorem stating the exact number.
  3. Standard memberChronicLeaky
    Don't Fear Me
    Reaping
    Joined
    28 Feb '07
    Moves
    655
    02 Mar '08 17:21
    Originally posted by ilywrin
    n+1 if I recall correctly. There is an Erdos-Szekeres Theorem stating the exact number.
    This is correct. Can you come up with the proof? It's come-up-with-able with little technicality, in the sense that more complicated arguments have been used to answer puzzles here, but it isn't at all easy.