Prove that for given integers $r, s$ any sequence of distinct real numbers of length at least $(r - 1)(s - 1) + 1$ contains either a monotonically increasing subsequence of length $r$, or a monotonically decreasing subsequence of length $s$.
Prove that every sequence of $n^2$ distinct numbers contains a subsequence of length $n$ which is monotone (i.e. either always increasing or always decreasing).
Posted: Jun 05 '12
Seen: 75 times
Last updated: Jun 12 '12