※ 引述《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)