※ 引述《nctupdc (交大布研)》之銘言：
: ※ 引述《mqazz1 (無法顯示)》之銘言：
: : 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
: : 請問這題該怎麼證明呢?
: ---
: 用反證法:
: 假設最大 length = n
: 先假設一 sequence: {a_i} , 1 ≦ i ≦ (n^2+1) 滿足題目所需
: 且定義 mapping 關係: f({a_i}, i) = ( x , y )
: 其中 x 代表存在最大的 length of increasing/decreasing subsequence
: y 代表在最大的 increasing/decreasing subsequence 下，
: 其 a_i 在此 subsequence 下的第幾個序列元素
: 可知 f({a_i}, i) = ( x , y ) , 1 ≦ x、y ≦ n
: 其值域共有 n^2 種可能
: 由 pigeonhole principle 可知
: 必然存在兩正整數 k、t , 1≦k＜t≦(n^2+1)
: 使得 f({a_i}, k) = f({a_i}, t) = ( x , y )
: → increasing/decreasing subsequence of length x 不可能同時存在
: 兩數 a_k 、 a_t , 皆對應到第 y 個序列元素
: 與假設矛盾
n=2
1,5,6,3,4
f( {a_2=5} ,2) = (3,2) (of seq 1,5,6)
f( {a_4=3} ,4) = (3,2) (of seq 1,3,4)
若是最大長度的seq不只一個
好像會有點問題
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 61.230.125.232
※ 編輯: nypgand1 來自: 61.230.125.232 (08/01 22:35)