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?
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.