※ 引述《mqazz1 (無法顯示)》之銘言： : Show that every real sequence with lm+1 terms contains either an : increasing subsequence with l+1 terms : or a decreasing subsequence with m+1 terms. 題目問 證明每個有nm+1個項目的實數序列中 (為免混淆 我把l改成n) 不是有長度為n+1的遞增子序列 就是有長度為m+1的遞減子序列 (附帶一提 遞增遞減子"序列"並不需要連續) 首先設序列的每個項目分別為a(1),a(2),......,a(nm+1) 而 x(k) 代表 從a(k)開始的"最長遞增子序列"的長度 for all k=1,2,...,nm+1 而 y(k) 代表 從a(k)開始的"最長遞減子序列"的長度 for all k=1,2,...,nm+1 用矛盾證法 假設序列a(1),a(2),......,a(nm+1)中 不存在長度為n+1的遞增子序列 也不存在長度為m+1的遞減子序列 則代表 1≦x(k)≦n 且 1≦y(k)≦m for all k=1,2,...,nm+1 將x和y組合成數對 （x(k),y(k)） 集合{（x(k),y(k)）| k=1,2,...,nm+1} 最多有nm個元素 (因為x(k)和y(k)的範圍限制) 而每一個a(k)都會對應到一個數對（x(k),y(k)） k=1,2,...,nm+1 從鴿籠原理得知 必定存在i,j且i≠j 使得（x(i),y(i)）＝（x(j),y(j)） 因為a(i)≠a(j) (題目沒有說每個項目皆相異...但好像要相異才能做?) 假如a(i)＜a(j) 則x(i)＞x(j) 矛盾（x(i),y(i)）＝（x(j),y(j)） 假如a(i)＞a(j) 則y(i)＞y(j) 矛盾（x(i),y(i)）＝（x(j),y(j)） 不管哪個都矛盾 所以得知假設錯誤 因此存在長度為n+1的遞增子序列 或存在長度為m+1的遞減子序列 -- 有錯請指正 謝謝~ --

※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 112.104.202.169 ※ 編輯: volleyer 來自: 112.104.202.169 (10/09 21:40)