推 nctupdc:剛剛看了一下，我的證明的確有兩個地方有問題 >_< 08/02 01:16
→ nctupdc:這篇的對應法比較好 :) 08/02 01:17
: 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
剛剛去辜狗了一下找到了一個解法
跟nctupdc板友的想法有一點類似
首先是subsequence的定義
Suppose that a_1,a_2, … a_n is a sequence of numbers.
A subsequence of this sequence is a sequence of the form a_i1, a_i2, …, a_im,
where 1 ≦ i1 < i2 < . . . < im ≦ n
所以對 11,19,110,7,5 來說
110,5是一個subsequence
[Page down方便閱讀]
接著我們對sequence內每一個數a_k都記錄兩筆資料(i_k,d_k)
i_k代表的是在原本的seq內從a_k往右選，可能達到最長遞增subseq的長度
d_k 減
舉個例子
8,11,9,1,4,6,12,10,5,7
a2 = 11 , (2,4) [編按：8,11 => i_2=2 11,9,6,5 => d_2=4]
a4 = 1 , (4,1)
建立好我們需要的資料後開始著手証明
我們假設沒有 長度≧n+1的increasing/decreasing subseq
所以 1≦ i_k , d_k ≦n for 整數k 1≦k≦(n^2+1)
i_k和d_k分別都有n種可能，(i_k,d_k)有n^2種組合
而我們剛剛說對每一個a_k都要記錄一組(i_k,d_k)
但是原seq總共有(n^2+1)這麼長
根據鴿籠原理
(n^2+1)個a_k 要分 n^2組(i_k,d_k)
一定存在兩個數a_s,a_t with s<t 分到重複的(i_s,d_s) = (i_t,d_t)
[Page down方便閱讀]
接下來我們要解釋分配到重複的pair會造成矛盾
因為題目說這些seq內的數字都是distinct
所以要嘛a_s<a_t要嘛a_s>a_t [編按：小提醒s<t]
如果a_s<a_t 那從a_s往右選的最長遞增subseq至少可能是
a_s再接上 a_t往右選的最長遞增subseq
這代表了i_s 至少有 i_t + 1 或是更大
與我們剛剛說的i_s=i_t，形成矛盾
同理，如果a_s>a_t
也會推到d_s≧d_t + 1
使得與d_s=d_t矛盾
所以假設錯誤
=> (n^2 + 1) 個distinct integers有長度≧n+1的increasing/decreasing subseq
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 61.230.125.232
※ 編輯: nypgand1 來自: 61.230.125.232 (08/02 01:00)