n^2+1高矮不等的人排成一列，总可以剔减成至少n+1 个人的顺高队列

jmyhyu

n²+1个高矮全不相等的人站成一排, 证明：总可以从中剔除若干人，使得剩下的队列是按从高到矮或者从矮到高的顺序排列的，并且剩余队列人数不少于n+1人。

sarda

这个很经典啊。每个人找个以该人开始最长的单增子列，设其长度为a_1,a_2,...,a_{n^2+1}。若有i使得a_i>n，证毕。否则存在n+1个a_i相同（抽屉原则）。从而这n+1个是以单减排列的(不妨设a_3=a_5，3号<5号。则5号存在一个以5号开始长为a_5的单增子列。在5号之前加上3号则变成一个以3号开始的长为a_5+1的单增子列。从而a_3>a_5，矛盾。)，找到一个长为n+1的单减子列。

suiyili

现在假想一个M*M的围棋网格(M > N)，把这群人想象成一列棋子，棋子上面编号代表人的高矮(乱续)。

好了，现在，从棋盘左上角开始放棋子，所有棋子都从左上角一个接一个入盘，规则是按照二叉树原则，如果新进入的棋子所走到的节点已有棋子，那么就和这个节点上的已有棋子比大小，如果新棋子比已有的棋子大，就向右进，比已有的棋子小的向下走。

假设第一个棋子是8，第二个是9,那么，第二个棋子(9)就将会在(0,-1)的位置，以此类推。这样变形二叉树的好处是，最右面和最下面的棋子分别代表最长递增和递减序列。

当你放下第N^2个棋子后，你会发现，如果棋子没有填满N*N方格内的每一个点，那么他们一定在横轴或者纵轴上超出了N。

如果正好都填满，那么，第N+1个棋子一定会在横轴或者纵轴上超出1，也就是N+1,所以，如题，最长单调序列至少为N+1。
————————————————————————————————
sheng_jianguo曾于2月14日8:25跟帖指出其中的一个小错误，已更正，sheng_jiang_jianguo的跟帖及有关后续帖因而被删除。------hujunhua

hujunhua

因此证明是不充分的。

1）即使二叉树突出n*n棋盘，也不能保证存在不短于n+1的棋子列或者行。至少楼上的说明是不充分的。
2）即使同一行/列，就算是连续的格子，也不能保证可保持原来的排列前后次序。

suiyili

1）即使二叉树突出n*n棋盘，也不能保证存在不短于n+1的棋子列或者行
可以保证的，假如最右一个棋子横向超出棋盘，就意味着存在某个序列从左上角开始一路下来(只能向右或向下)，踩着有子的格子一路走到最右边的棋子（只存在一条路径），其中向右的步数一定大于等于n+1.
2）即使同一行/列，就算是连续的格子，也不能保证可保持原来的排列前后次序。
不能用同一行/列判断，要从左上角开始按照向右或向下原则判断，任何右下的棋子一定后于其左上的棋子进入棋盘。所以是从某一左上角起点的，向右下走的序列中，保持原来的排列前后次序

suiyili

上面二点说的不全面，这里修正

2）即使同一行/列，就算是连续的格子，也不能保证可保持原来的排列前后次序。
应该说，任何一个棋子都可以从左上角寻径下来，其径就是该子当时从左上角进入棋盘时（按照二叉树原则）走过的路经，而在此路经上的棋子，是保持原来未进入棋盘前的前后排列次序的。

1）即使二叉树突出n*n棋盘，也不能保证存在不短于n+1的棋子列或者行
假如最右一个棋子横向超出棋盘，就意味着回答2）中提到的路经中向右的步数一定大于等于n+1

suiyili

关于我的以上两个回帖仔细推敲都有错误，关键问题出在我第一次回贴中的关于最右及最下棋子为最长递增及递减序列，也就是重新编辑后的红字部分。多谢几位大虾提醒，确实是个漏洞，需要证明。

现在试证，假设现在有一个子从左上角进入棋盘后，按照二叉树原则行走，如果它是第一个从右侧突破第n行的棋子（在第n+1行），设它为A(n+1),那么它一定是踩着它左边那个棋子走来的，那么它左边的那个棋子设为A(n),在第n行。可以推定，A(n)一定先于A(n+1)到达棋盘，也一定小于A(n+1)。

同理，在第n-1行也一定存在一个A(n-1)先于A(n)到达并且小于A(n),因为A(n)如果不是踩着自己左边的棋子到达它现在的位置，那也一定是踩着自己上面的棋子过来的，而A(n)上面的棋子一个踩一个，总有一个（顶多到这一列的最上一个）是要踩着自己左边的棋子A(n-1)来的.

这样A(i) 一定先于并且小于A(j) , 其中i < j。而从A(n+1)到A(0)一共有n+1 个，符合递增序列至少为n+1.
同理，也可证明递减序列。

hujunhua

楼上的思路是正确的，这回终于说透了。楼上“行”皆改为“列”比较符合习惯。

按矩阵的角标，从(1, 1)开始。那么自(a,b)子回溯，存在长为a的递减子列和一个长为b的递增子列。
(a, b)子的进入路线是一条右下向的阶梯形折线，回溯时的第１个拐角如下图红色部分所示，可能是└形或者┐形。
──┐　　　　　　　──┐
　　└┐　　　　　　　　└┐
　　　│　　　　　　　　　│
　　　│　　　　　　　　　└┐
　　　└─　　　　　　　　　│
1）长为a递减子列
记(a,b)子为$P_a$，红色拐角的水平边与(a-1)列线交点处的子记为$P_{a-1}$. 显然，$P_{a-1},P_a$是一个递减子列。
同理，由$P_{a-1}$回溯也可以在(a-2)列线上找到$P_{a-2}$,使得，$P_{a-2},P_{a-1}$是一个递减子列，因此$P_{a-2},P_{a-1},P_a$是一个递减子列。依此往溯，就可以得到一个递减子列$P_1,P_2,...,P_{a-1},P_a$.

2)长为b递增子列
记(a,b)子为$Q_b$，红色拐角的竖直边与(b-1)行线交点处的子记为$Q_{b-1}$....

mathe

我们是否可以得出另外一个计数问题：
将n^2个高矮各不相同的人排成一列，使得所有递增和递减的子列的长度都不超过n,那么请问有多少种不同的哦排列方法

hujunhua

确实是个问题。不过是否存在简明答案就不一定了。
先定义几个术语便于后续讨论时统一使用。觉得不贴切的，咱们按建议可以改进。
定义1（均混排列） 1, 2, 3, ..., n^2的一个排列，其中任何单调子列的长度都不超过n的排列称为均混排列。
定义2 （二叉阵）3#所述的那种变形二叉树且称为二叉阵。

均混排列对应的二叉阵刚好四四方方地填满n×n矩阵，但刚好四四方方地填满n×n矩阵的排列不一定就是均混排列。

定义3（方排列）二叉阵恰好是一个n×n矩阵的排列称为方排列。

从排列->二叉阵是单射，反过来不是。