韦东奕封神之题——2009IMO蚱蜢跳跃题详解,看完解析你也能做
引言
本文给出 2009 年第五十届 IMO 压轴第六题的详细解答,据传当年韦东奕凭借此题甚至“击败”了陶哲轩。据悉,陶哲轩耗费 7 个小时才解决此题,而韦东奕仅花费 1 小时。本文给出的解答带有一些原创思路,适合高中学历读者。
问题
设
是互不相同的正整数,
是有
个元素的正整数集,且不含数
一只蚱蜢沿着实数轴从原点 0 开始向右跳跃
步,跳跃距离是
的某个排列。
证明:存在某个排列,使得蚱蜢跳跃落下的点所表示的数都不在
中。
分析
我们用
表示
的前
项和数列,即
,
,那么这道题的意思就是,让我们找出
的某个排列,使得对于任意正整数
,
这意味着在数轴上,数列
和
中的数是错开排列的,即没有重合的点,例如下图所示。
而其中一种反例如下图所示(这种情况下
)
为了构造出这样一种情况,我们会时常交换数列
中某两项的位置,而为了很好地分析交换后各个点的移动情况,我们不妨一开始就对数列
进行大小排序,即我们不妨假定
在这种假设下,我们可以考虑下面两种变换模型。
模型 1:交换
如上图所示,由于
,那么交换
之后,它们之间的点全部向右移动,即s_k,'>
,其他的点则保持不动。
模型 2:将
移动到
后面
,之间的部分往前移。
类似模型 1,这样操作之后,
之间的点同样全部向右移动。与之不同的是,这种模型下必然有<>
这条结论之后会用到。
上面列举的两个模型,在解答中必然会用到,它们的性质比较显而易见,严格证明留给读者思考。接下来提供本题的解答。
解答
我们将证明以下命题:
命题:设
是互不相同的正整数,记
,
,
是一个集合,其中的元素都为正整数。对于任意正整数
,若有
,
即区间
至多包含
个
中的元素,
则存在
的某个排列
,使得
对于
恒成立,其中
对于
恒成立。此时,
的位置是不会改变的,即
,又由条件
,故
对于
恒成立。
推论 1 的证明:
与
的位置关系如上图所示。从右往左看这幅图,则变为引理 1 讨论的情况,故易知推论成立。证毕。
引理 2:若存在正整数
使得
,记
的子集
,则存在
的某个排列
,使得<>
,并且
引理 2 的证明:各点的位置关系如上图所示。我们使用模型 2 ,将某个
拿出来放到
后面,中间的部分往前移,那么各点的位置将变成下图所示。
此时,
是保持不动的,即
,我们有
以及
即<>
满足题设,故只要说明,存在某个
,使
即可。
考虑所有的二元组
,一共有
组,从而总共有
个数。这
个数必然两两不相等:一方面对于
必然有
,必然有
以及
,另一方面对于任意
,必然有
故它们两两不相等。我们把这
个数的集合暂记为
。假如任意一个二元组中都至少有一个数属于
,则至少
个数属于
,即
,但另一方面,由于
,而
,故
此时
(
去掉一个数还剩
个数),这与
相矛盾。故存在某二元组
中的两个数都不属于
,即取
,可使得
。证毕。
推论 2:若存在正整数
使得
,并且
,则存在
的某个排列
,使得<>
,并且
。
推论 2 的证明:由于
则
必然是
的一个子集,则由引理 2 知结论成立。证毕。
引理 3:若存在正整数
使得
,则存在
的某个排列
,使得m_q'>
,并且
,根据
的数量,
,再由s_p=m_q'>
知结论成立。证毕。
回到原题的证明,我们分各种情况讨论。
情况 1:若
对于
恒成立,则分两种情况:
情况 1.1:若
,则
,根据引理 1 知结论成立。
情况 1.2:若
,由于
,则存在
,使得
,其中
相关点的分布如下图所示。
我们使用引理 2,将
排列成
,使得<>
,且
如下图所示。
注意到
在这种排列下保持不动,即m_1">
,各点位置关系如下图所示。
根据推论 1 知结论成立。
情况 2.1.2:若
,则
,使用引理 3 ,将
排列为
,此时m_1'>
,并且m_{t}">
,这依旧属于情况 2.2.1。
情况 2.2.2.2.2:若<span data-content="{"url":"//image109.360doc.com/DownloadImg/2021/06/0616/223626813_241_20210606044404833","uri":"pgc-image/cbd3893f05254c34b1c2a764c4c3a71b","width":64,"height":27,"darkImgUrl":"https://p5.toutiaoimg.com/origin/pgc-image/4a21e0e2fc134a9ca414033f56dd7a9b","darkImgUri":"pgc-image/4a21e0e2fc134a9ca414033f56dd7a9b","formulaImgStatus":"succeed"}" data-formula="s" _{t}\in="" m'="">
,则
,则存在
,使得
。此时各点的位置关系如下图所示。
我们使用引理 3,将
排列为
,使得<span data-content="{"url":"//image109.360doc.com/DownloadImg/2021/06/0616/223626813_248_20210606044405411","uri":"pgc-image/0aa69b73e70a4051aa18f9588bd38753","width":72,"height":27,"darkImgUrl":"https://p5.toutiaoimg.com/origin/pgc-image/a8ff863dd3e94bbc8c328ba678fb1044","darkImgUri":"pgc-image/a8ff863dd3e94bbc8c328ba678fb1044","formulaImgStatus":"succeed"}" data-formula="s" '_{t}="">m_{q}'>
,并且
此时,<span data-content="{"url":"//image109.360doc.com/DownloadImg/2021/06/0616/223626813_250_20210606044405678","uri":"pgc-image/d042c688884b48bd87bf760aece9046e","width":35,"height":27,"darkImgUrl":"https://p3.toutiaoimg.com/origin/pgc-image/1ee9ccbf64604b6291290d62ffc81b38","darkImgUri":"pgc-image/1ee9ccbf64604b6291290d62ffc81b38","formulaImgStatus":"succeed"}" data-formula="s" _{t-1}'="">
位置不变,即< m_{t-1}'="">
,而<span data-content="{"url":"//image109.360doc.com/DownloadImg/2021/06/0616/223626813_252_20210606044405755","uri":"pgc-image/3729aa06ba424864bb8694f507e4ebba","width":125,"height":27,"darkImgUrl":"https://p6.toutiaoimg.com/origin/pgc-image/a0ce40e1aab8473fb41316cf39d41d01","darkImgUri":"pgc-image/a0ce40e1aab8473fb41316cf39d41d01","formulaImgStatus":"succeed"}" data-formula="s" '_{t}="">m_{q}\geq m_{t}'>
,这同样属于情况 2.2.1。
情况 2.2.2.3:若m_{t-1}'>
且
,使得
。此时各点的位置关系如下图所示。
容易看出这属于 情况 2.2.2.2.2。
综上所述,由数学归纳法知命题是成立的。证毕。
总结
这道题我思考了两个小时,讨论出了大部分情况,但依旧有遗漏一两种情况,看了答案才豁然开朗,事实上类似模型 2 的操作并不容易想到。这道题涉及的计算量并不多,但是对分类讨论的要求特别高,很容易遗漏。
本题的答案很多都使用作图来描述,其实很多不等关系使用数轴画出来则一目了然,这是本文比一般解答细致的地方,可读性更高。
做过此题之后,才体会到此题确实有难度,虽然做出来不是完全不可能,但是临场考试做出来的可能性确实不大,会耗费很多时间。在此,膜拜一下韦东奕大神!
这个答案比较泛泛而谈,虽然都正确,但有的复杂结论一句话带过,可阅读性不高,因此需要详解。