题目：
任意mn+1个不同的数排成一列，求证：要么存在m+1项递增数列，要么存在n+1项递减数列
一、分析
为什么要任意mn+1个数呢？是不是说明mn个数存在不满足的情况？我们可以先尝试寻找mn个数的情况
我们发现： n,n-1,...,1, 2n,2n-1,...,n-1, ......, mn,mn-1,...,(m-1)n+1
以上的这个数列有mn个数，且不存在m+1项递增数列，也不存在n+1项递减数列
那这样的话，想证明mn+1满足，我们就用反证法好了
二、证明
假设没有m+1项递增数列，则我们只要证明存在n+1项递减数列即可
考查以每一项为起点的单增子列的长度
例如：
数列：1,7,2,5,10,6,9
长度：5,2,4,3,1,2,1
一共有mn+1个起点，而每个长度必须在1~m中，根据抽屉原理，必有n+1个起点对应的长度相等
而这n+1的起点必然递减，证明如下：
设第i个数的值为ai，以i为起点的单增子列的最大长度为bi
如果存在i,j，使得i<j，若ai<aj，那么以i为起点的单增子列长度应该是以j为起点的单增子列的长度，即bi=bj+1
此时bi≠bj，与要求矛盾
因此这n+1个起点必然递减
这样我们就找到了长度为n+1的递减子列
命题得证
标签：数列,mn,个数,数学,经典,长度,递减,抽屉,起点 From： https://www.cnblogs.com/hzy-ygkl/p/17367422.html