【高手入】有道难题，求高手帮忙

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

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

标准版

全部回复 (9)

沙发回复于 2012-11-25T04:59:35.000Z

3345678

好像看懂了。。。。

回复(0)标准版

板凳回复于 2012-10-24T08:21:04.000Z

轻舟过

自古元首幸运E 发表于 2012-10-24 15:59 【链接登录后可见】
太感谢了，我都懂了。 (另：我超喜欢你的博客，你是学过编程奥赛的吧？） ...

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

回复(0)标准版

地板回复于 2012-10-24T07:59:07.000Z

自古元首幸运E

轻舟过发表于 2012-10-24 14:13 【链接登录后可见】
说是有n种取值，实际上是排除了不能取大于等于n+1的情况剩下可能的取值啦 ...

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

回复(0)标准版

5 楼回复于 2012-10-24T06:13:42.000Z

轻舟过

自古元首幸运E 发表于 2012-10-24 13:19 【链接登录后可见】
我理解了后面的那部分，但是不理解前面的一个地方：这是假设不存在n+1而存在能排列n个递减子序列或递增子 ...

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

回复(0)标准版

6 楼回复于 2012-10-24T05:19:39.000Z

自古元首幸运E

轻舟过发表于 2012-10-24 10:49 【链接登录后可见】
这题是我们离散课课本上的例题
拿出来翻了下，是这样证明的：（_k表示下标k）
设a_1,a_2\ldots, a_{n^ ...

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

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

回复(0)标准版

7 楼回复于 2012-10-24T05:04:45.000Z

自古元首幸运E

自古元首幸运E 发表于 2012-10-24 12:58 【链接登录后可见】
“i_k只有1～n这n种取值，d_k也只有1～n这n种取值”不太懂。n应该是队列中的人数，这里的“1～n这n种取值 ...

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

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

回复(0)标准版

8 楼回复于 2012-10-24T04:58:18.000Z

自古元首幸运E

轻舟过发表于 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应该是队列中的人数，这

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

回复(0)标准版

9 楼回复于 2012-10-24T02:49:30.000Z

轻舟过

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

这题是我们离散课课本上的例题
拿出来翻了下，是这样证明的：（_k表示下标k）
设a_1,a_2\ldots, a_{n^2+1}为一排人的高度，对每个a_k，定义数对【链接登录后可见】，i_k为从a_k开始最长的递增子序列，d

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

回复(0)标准版

10 楼回复于 2012-10-23T23:31:48.000Z

自古元首幸运E

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

回复(0)标准版