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