Re: [理工] 離散-鴿籠原理證明

[mqazz1 (無法顯示)]

※ 引述《showyoulovex (NONO)》之銘言：
: 題目(已縮圖):http://ppt.cc/dU9n
: 麻煩各位了
: 這題好難想好久還是不知道該怎樣下手

如果題目只有幾行字的話 建議打出來會比較好@@

因為通常回答者要打的字會更多..

===============================================

假設數列是a(1)到a(n^2 + 1)

令 lengI(k), lengD(k) 為由a(k)開始最長的遞增跟遞減subsequence

若a(1)到a(n^2+1)不存在長度n+1的subsequence

1 <= lengI(k), lengD(k) <= n

| {(lengI(k),lengD(k))} |  <=  n^2

因此由鴿籠得知 必有兩個(lengI(k),lengD(k))是相同的

因為題目說 a(k) 都是不同的

再分兩個case來看

1. a(i) > a(j)   =>   lengD(i) > lengD(j), 和鴿籠得到的矛盾

2. a(i) < a(j)   =>   lengI(i) > lengI(i), 和鴿籠得到的矛盾

所以這兩個都不可能成立

整個命題得到矛盾

所以原命題得證

--
※ 發信站 :批踢踢實業坊(ptt.cc)
◆ From: 140.118.110.186
推 RebeccaHall:推~蠻精簡的..我看書上解答寫好長
→ mqazz1:因為這題我之前也是想了好久 黃子嘉解的好像很長
※ 編輯: mqazz1          來自: 140.118.110.186      (10/14 18:37)
推 RebeccaHall:是超長~考試時間就不太夠了...
→ mqazz1:所以可能鴿籠的問題 理解後就直接背了 不然沒時間想思考題
推 showyoulovex:感謝大大解答與建議  感謝