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