drawer principle in Combinatorics

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 ≤ a_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 a_ki < a_kj,

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

drawer principle in Combinatorics

原文：http://www.cnblogs.com/astoninfer/p/5014063.html