Re: [理工] [離散] 鴿籠原理
※ 引述《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)
推
08/01 21:55, , 1F
08/01 21:55, 1F
推
08/01 21:58, , 2F
08/01 21:58, 2F
推
08/01 22:14, , 3F
08/01 22:14, 3F
討論串 (同標題文章)