→ ieric:集合只有n^2 種 但有n^2+1個數 所以存在兩組相等 06/25 12:49
→ ieric:後面就是利用矛盾"假設不存在長度為n+1" 得到證明的解 06/25 12:53
→ ieric:上面應該寫成n^2+1組集合 比較好@@ 06/25 12:56
※ 引述《Austin9 (奧斯丁)》之銘言：
: Show that in a sequence of (n^2 + 1) distinct integers, there is either an
: increasing subsequence of length n + 1 or a decreasing subsequence of length
: n + 1.
: 請問一下，有人可以舉例稍微說明一下嗎？謝謝。這題有解答，但解答有點難懂，
: 不知道是否有例子可以看呢？謝謝。
: n^2 + 1 這地方好難想像哦！
: 解答上的例子是{1,3,2,4,9,7}怎麼套進n^2+1呢？
不好意思，有人可以解惑一下嗎？看能不能用較簡單的方式舉例一下，因為有點
難想像說，謝謝。
解答是這樣
假設這n^2+1個整數序列為a1,a2..an^2+1,令xk及yk分別表示由ak開始最長的遞增及
遞減子序列的長度,k=1,2...n^2+1假設該整數序列a1,a2...an^2+1中不存在長度為
n+1的遞增子序列且不存在長度為n+1的遞減子序列
從這以下就不懂了，集合是要做啥用的啊？
則1≦xk,yk,≦n,for all k=1,,2....n^2+1
所以集合{(xk,yk)|k=1,2....n^2+1}的元素個數最多為n^2個
由於每個ak唯一對應一組(xk,yk) for all k=1,2,...n^2+1
by pigeonhole知存在i,j,i＜j,使得(xi,yi)=(xj,yj)
因為ai≠aj
若ai<aj,then xi>xj, so (xi,yi)≠(xj,yj) -><-
若ai>aj,then yi>yj, so (xi,yi)≠(xj,yj) -><-
所以存在長度為n+1的遞增子序列或長度為n+1的遞減子序列
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 27.105.35.9