本帖最后由 自古元首幸运E 于 2012-10-24 07:32 编辑

n^2+1个高矮全不相等的人站成一排, 证明：总可以从中按顺序选出不少于n+1人，使得选出的队列是按从高到矮或者从矮到高的顺序排列的

好像看懂了。。。。

自古元首幸运E 发表于 2012-10-24 15:59 【链接登录后可见】

太感谢了，我都懂了。 (另： 我超喜欢你的博客，你是学过编程奥赛的吧？） ...

不客气

我只是跟ACM校队的人混过一段时间而已

轻舟过 发表于 2012-10-24 14:13 【链接登录后可见】

说是有n种取值，实际上是排除了不能取大于等于n+1的情况剩下可能的取值啦 ...

太感谢了，我都懂了。@@32!! (另： 我超喜欢你的博客，你是学过编程奥赛的吧？）

自古元首幸运E 发表于 2012-10-24 13:19 【链接登录后可见】

我理解了后面的那部分，但是不理解前面的一个地方：这是假设不存在n+1而存在能排列n个递减子序列或递增子 ...

说是有n种取值，实际上是排除了不能取大于等于n+1的情况剩下可能的取值啦

轻舟过 发表于 2012-10-24 10:49 【链接登录后可见】

这题是我们离散课课本上的例题

拿出来翻了下，是这样证明的：（_k表示下标k）

设a_1,a_2\ldots, a_{n^ ...

我理解了后面的那部分，但是不理解前面的一个地方：这是假设不存在n+1而存在能排列n个递减子序列

【查看更多内容请登录哈】

自古元首幸运E 发表于 2012-10-24 12:58 【链接登录后可见】

“i_k只有1～n这n种取值，d_k也只有1～n这n种取值”不太懂。n应该是队列中的人数，这里的“1～n这n种取值 ...

我理解了后面的那部分，但是不理解前面的一个地方：这是假设不存在n+1的情况而存在n个递减子序列或

【查看更多内容请登录哈】

轻舟过 发表于 2012-10-24 10:49 【链接登录后可见】

这题是我们离散课课本上的例题

拿出来翻了下，是这样证明的：（_k表示下标k）

设a_1,a_2\ldots, a_{n^ ...

“i_k只有1～n这n种取值，d_k也只有1～n这n种取值”不太懂。n应该是队列中的人数，这里

【查看更多内容请登录哈】

本帖最后由 轻舟过 于 2012-10-24 10:51 编辑

这题是我们离散课课本上的例题

拿出来翻了下，是这样证明的：（_k表示下标k）

设a_1,a_2\ldots, a_{n^2+1}为一排人的高度，对每个a_k，定义数对【链接登录后可见】，i_k为从a_k开始最长的递增子序列，d_

【查看更多内容请登录哈】

想了好久啊，见到有人在这里讨论： http://bbs.emath.ac.cn/thread-2931-2-1.html 不过好像最后也没定论。。。