→ QoGIVoQ: 弄清楚了 感謝 10/02 12:01
※ 引述《QoGIVoQ (瓏瓏小於三)》之銘言：
: 題目如圖
: https://i.imgur.com/KXmZfiS.jpg
: 這題是要證明
: 遞增和遞減存在長度n+1
: 所以用n^2+1和n^2來做鴿籠嗎
: 解答用的矛盾法有點看不懂
這題要證明
存在 含有n+1個數的遞增數列 或 含有n+1個數的遞減數列
所以用反證法
先假設 不存在n+1個數的遞增數列 且 不存在n+1個數的遞減數列
言下之一
每個從a_k開始的最長的遞增數列所含的數字個數只會為1~n中的一個數，稱x_k
每個從a_k開始的最長的遞減數列所含的數字個數只會為1~n中的一個數，稱y_k
所以數對(x_k, y_k)的所有可能為n^2個可能。
但是我們有n^2 + 1個數，
因此可以有n^2 + 1個數對，
依據鴿籠原理
必然至少存在兩個相異數i < j，
他們各自的數對是相同的 => (x_i, y_i) = (x_j, y_j) -------(*)
但是別忘了原數列中a_i和a_j不知誰大誰小
如果a_i < a_j，
最大長度為x_i的遞增數列必包含a_j，代表x_i > x_j => 與(*)矛盾
如果a_i > a_j，
最大長度為y_i的遞減數列必包含a_j，代表y_i > y_j => 與(*)矛盾
所以原命題得證。
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 111.243.62.178
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1538394637.A.D4C.html