求证能使其余$n+1$个数递增或递减排列

abababa

求证数码$1,2,3,\cdots,n^2+1$的任意排列中，总能抹去其中$n(n-1)$个数，使得其余$n+1$个数递增或递减排列

abababa

发一位网友的证明
设排列$a_1,\cdots, a_i$中最长增子列和最长减子列项数为$p_i,q_i$
假设$1 \le p_i,q_i \le n$，则由乘法，序偶$(p_i,q_i)$少于$n^2$个，而$i$有$n^2+1$个，由抽屉，$\exists i_1 < i_2 \to (p_{i_1},q_{i_1})=(p_{i_2},q_{i_2})$
显然$a_{i_1} \neq a_{i_2}$，但$a_{i_1}<a_{i_2}$时必有$p_{i_1}<p_{i_2}$，$a_{i_1}>a_{i_2}$时必有$q_{i_1}<q_{i_2}$，都不能使$(p_{i_1},q_{i_1})=(p_{i_2},q_{i_2})$
于是假设错误，所以存在$i$使得$p_i \ge n+1 \lor q_i \ge n+1$
这显然使得命题成立，只要从$p_i$或$q_i$项中选择$n+1$个并抹去其余

realnumber

2楼看不懂,有没别的证明?

abababa

回复 3# realnumber

是不是那个$a_{i_1}<a_{i_2}$时必有$p_{i_1}<p_{i_2}$的地方说的不太明白？
我开始就是这里看不明白，我觉得他这个证明如果能证明末尾的数或者在最长的增子列中，或者在最长的减子列中，这个地方就很明显了，但是我还没有证明到这一点

realnumber

回复 4# abababa

2楼,"而i有n2+1个，由抽屉，",这里开始就模糊了,明明在说坐标少于n^2,怎么抽屉说的是整数个数是n^2+1.
4楼,你说的还没开始,前面没明白,已经堵塞了.

abababa

回复 5# realnumber

因为$(a_1,a_2,a_3,\cdots,a_i)$这里最长的增子数列项数是$p_i$，现在又假设了$p_i \le n$，那么$p_i$最多就有$1$到$n$这$n$个值，同样$q_i$也最多有$n$个值，这样先取$p_i$再取$q_i$，按乘法原理就是至多有$n^2$个值。他说少于$n^2$个没说准确，应该可以等于$n^2$个
然后$(a_1,a_2,a_3,\cdots,a_i)$这里的$i$可以从$1$到$n^2+1$，总共是$n^2+1$个这样的组，所以$i$总共有$n^2+1$种取法

关键是把物品和抽屉都集中到$i$上，从$i$可以构造出的抽屉$(p_i,q_i)$不超过$n^2$个，从$i$构造出的物品是$n^2+1$个

goft

本题等价于$n*n$个数必有一列（或行）$n$个数递增或递减

realnumber

回复 7# goft
应该不是的。
看这个3×3
164
758
293

realnumber

一个n个不同整数的乱序中，最大递增（减）子数列长度，这两个长度有没简洁的关系？