首页 > 代码库 > 单调序列 Proofs from THE BOOK chapter22

单调序列 Proofs from THE BOOK chapter22

此书的22章讲到了鸽笼原理,其中一道题挺有意思

在任何一个大小为mn+1的序列,a1, a2,..., 每个实数各不相同。要么存在一个大小为m+1的递增序列,要么大小为n+1的递减序列,或者同时存在。 









下面是书中给出的解答:

先做个定义:对于某个ai,都有一个ti代表了以ai为起始点的最大上升序列的长度。

举个例子m=2,n=2的序列

1 2 -1 0 3

相应的ti序列就是

3 2 3 2 1


1)如果ti>=m+1,那么存在一个m+1的递增序列,问题得证明。

2)那么假定所有ti<=m。总共有mn+1个t,它的取值范围是{1,...,m}。根据鸽笼原理,那么有n+1个数具有相同t值。

假定这个值为s,且1<= s <= m。

考察这n+1个数{a(j,1),a(j,2),...,a(j, n+1)},我们可以得到这样的结论a(j,1) >a(j,2)>...>a(j,n+1)

为什么呢?如果相邻的两个数a(j, i)<a(j, i+1)。以a(j, i+1)开头已经有长度为s的递增序列了,再加上a(j, i), 就会找到以a(i,j)为开头的递增序列长度为s+1。与原先的假设矛盾!

根据a(j,1) >a(j,2)>...>a(j,n+1),我们可以得到一个长度为n+1的递减序列。问题的证


说说我的解题思路:

对于每一个ai,定义以它为结尾的最大递增,递减序列长度分别为(xi, yi)

1)如果xi>=m+1,或则yi<=n+1,那么问题得证!

2)我们假定1<=xi<=m,且1<=yi<=n。

首先我们可以得到任意两对(xi, yi) (xj, yj)不完全同。如果完全相同,会存在矛盾

例如ai 的是(3, 5), aj的也是(3,5)。如果ai<aj,那么实际可以找到一个以aj为结尾的长度为4的单调递增序列。ai>aj也是同理。

由于xi, yi的取值范围,总共只有mn对完全不同的数。

例如m=2, n=3,只有(1,1 (1,2) (1,3) (2,1) (2,2) (2,3)

但是我们有mn+1对(xi, yi),必然存在两对数完全相同,与上述的推论“任意两对(xi, yi) (xj, yj)不完全同”矛盾。因为有mn个笼子和mn+1只鸽子。

因此命题的得证

单调序列 Proofs from THE BOOK chapter22