※ 引述《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://webptt.com/m.aspx?n=bbs/Grad-ProbAsk/M.1538394637.A.D4C.html