推 nypgand1:請問這個方向要怎麼配合說明一定有一個存在呢 08/01 21:55
推 nypgand1: ^subsequence 08/01 21:58
推 nypgand1:好像看懂了 謝謝 08/01 22:14
※ 引述《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 個序列元素
與假設矛盾
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.113.47.130
※ 編輯: nctupdc 來自: 140.113.47.130 (08/01 21:16)