Please turn on javascript in your browser to play chess.
Posers and Puzzles

Posers and Puzzles

  1. Standard member ChronicLeaky
    Don't Fear Me
    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. 01 Mar '08 08:32
    n+1 if I recall correctly. There is an Erdos-Szekeres Theorem stating the exact number.
  3. Standard member ChronicLeaky
    Don't Fear Me
    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.