向陆教授请教一题

simpley

[这个贴子最后由simpley在 2010/08/04 08:27pm 第 1 次编辑]

我想了很久，得不到结果。
书上的证明是用鸽巢定理证的，我看了认为毫无道理。
N^2+1个数中，至少存在一个长度为N+1的递增或递减数列。

luyuanhong

下面引用由simpley在 2010/08/04 08:26pm 发表的内容：
我想了很久，得不到结果。
书上的证明是用鸽巢定理证的，我看了认为毫无道理。
N^2+1个数中，至少存在一个长度为N+1的递增或递减数列。

请你把书上的证明原原本本详详细细写出来，让我看看是不是有道理。

simpley

书上的证明如下: 令长度N^2+1的数列为(S1,S2,......SN^2+1),以SI为基准,在(SI,SI+1,....SN^2+1)中找出一个最长的递增数列和最长的递减数列,递增数列长度分别是II,递减数列长度是DI. 设II,DI同时小于N。将II,DI配对，则（II,DI）∈P={(1,1),(1,2),...(1,N),(2,1)...(N,N)}.(1,1)对应鸽巢1,(1,2)对应鸽巢2,(N,N)对应鸽巢N^2.令（II,DI）为第I只鸽子的编号，且飞入对应的鸽巢，因为1<=I<=n^2+1,所以共有n^2+1个鸽子，一定至少有一个鸽巢聚集了两个以上的鸽子. （我认为下面的推理就完全不通了） 设这在同一鸽巢的两个鸽子的编号为（IK1，DK1），（IK2，DK2），且K2>K1.因为K2>K1，表示介于SK1到SK2之间的数均大于SK2。如此一来，可在SK1到SK2-1之间找到一个数并且可纳入IK1所对应的递减数列，就得到一个长度大于DK1的递减数列，这是矛盾的。故命题成立 请陆教授给予指导。

luyuanhong

[这个贴子最后由luyuanhong在 2010/08/18 10:36pm 第 2 次编辑]

下面引用由simpley在 2010/08/18 03:51pm 发表的内容： 书上的证明如下: 令长度N^2+1的数列为(S1,S2,......SN^2+1),以SI为基准,在(SI,SI+1,....SN^2+1)中找出一个最长的递增数列和最长的递减数列,递增数列长度分别是II,递减数列长度是DI. 设II,DI同时小于N。将II,DI配对，则（II,DI）∈P={(1,1),(1,2),...(1,N),(2,1)...(N,N)}.(1,1)对应鸽巢1,(1,2)对应鸽巢2,(N,N)对应鸽巢N^2.令（II,DI）为第I只鸽子的编号，且飞入对应的鸽巢，因为1<=I<=n^2+1,所以共有n^2+1个鸽子，一定至少有一个鸽巢聚集了两个以上的鸽子. （我认为下面的推理就完全不通了） 设这在同一鸽巢的两个鸽子的编号为（IK1，DK1），（IK2，DK2），且K2>K1.因为K2>K1，表示介于SK1到SK2之间的数均大于SK2。如此一来，可在SK1到SK2-1之间找到一个数并且可纳入IK1所对应的递减数列，就得到一个长度大于DK1的递减数列，这是矛盾的。故命题成立 请陆教授给予指导。

原证明可能是从外文翻译过来的，没有翻译好，所以其中的推理，确实有些讲不通。 我给出此题的证明如下：

simpley

上面的证明主要是说有一个鸽巢聚集了两个以上的鸽子是不可能的,但实际上却是可能的.
比如,（6,9，4）的最长递增数列和递减数列长度都是2
（6,9,4,5）也是2

simpley

非常感谢.
陆教授不仅数学功底深厚,而且乐于助人,令人钦敬.