Problem 1: Given an array of real number with length (n² + 1) A:

a₁,  a₂, ... , a_n²+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 m_i denote

the length of the longest increasing subarray(LIS) beginning with element a_i , thus under the assumption above we

have: for all 1 ≤ i ≤n² + 1, 1 ≤ m_i ≤ n. Therefore by drawer principle we have m_k1 = m_k2  = _...  = m_k(n+1),(k₁ < k₂ <... < k_(n+1)).

(otherwise we have n² numbers at most whilst we got n² + 1).We assert that's the disired decreasing array, otherwise if (ki , kj) :

 a_ki < a_kj ,we have LIS(m_ki) ≥ LIS(mkj) + 1, and this results a contradiction.