Re: [理工] [離散] increasing subsequence
※ 引述《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)
推
10/09 21:56, , 1F
10/09 21:56, 1F