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 ilywrinThis 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.
n+1 if I recall correctly. There is an Erdos-Szekeres Theorem stating the exact number.