Problem 1: Given an array of real number with length (n2 + 1) A:
a1, a2, ... , an2+1.
Prove that there is either an increasing or a decreasing subarray of A with length (n + 1).
Proof:
In order to prove the proposition, we just need to prove that there must be a decreasing subarray of A
with length (n + 1) when there doesn't exist an increasing subarray of A with length (n + 1). Let mi denote
the length of the longest increasing subarray(LIS) beginning with element ai , thus under the assumption above we
have: for all 1 ≤ i ≤n2 + 1, 1 ≤ mi ≤ n. Therefore by drawer principle we have mk1 = mk2 = ... = mk(n+1),(k1 < k2 <... < k(n+1)).
(otherwise we have n2 numbers at most whilst we got n2 + 1).We assert that's the disired decreasing array, otherwise if (ki , kj) :
aki < akj ,we have LIS(mki) ≥ LIS(mkj) + 1, and this results a contradiction.