Show that every sequence a1, a2, ... ,a的n平方+1 有n平方+1個數，有包含長度為 n + 1 的遞增序列 or a 長度為 n + 1 的遞減序列 離散數學求解QQ?

若數列 a1 , a2 , ... , a_(n²+1) 中包含長度為 n + 1 的遞增序列, 則命題已經成立。

若數列 a1 , a2 , ... , a_(n²+1) 中不包含長度為 n + 1 的遞增序列,
記以 a1 , a2 , ... , a_(n²+1) 為首項的最長遞增序列長度分別為 L1 , L2 , ... , L(n²+1),
則 1 ≤ L1 , L2 , ... , L(n²+1) ≤ n。
若每個 L 的可能值至多有 n 個, 則數列中最多有 n × n = n² < n²+1 個數矛盾!
故必存在某個 L (其中1 ≤ L ≤ n) 的值至少有 n+1 個。

於是在數列中可找到 n+1 個數依序為 a1' , a2' , ... , a(n+1)' (其中 1 ≤ 1' < 2' < ... < (n+1)' ≤ n²+1),
以它們為首的最長遞增序列都等長, 而且對它們任何兩個連續項而言前一項必大於後一項, 否則以前一項為首的最長遞增序列將比以後一項為首的最長遞增序列的長度要大1, 矛盾!
故必有 a1' > a2' > ... > a(n+1)' , 此即為長度是 n + 1 的遞減序列 , 故命題得證。