韦东奕封神之题——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 的操作并不容易想到。这道题涉及的计算量并不多,但是对分类讨论的要求特别高,很容易遗漏。

本题的答案很多都使用作图来描述,其实很多不等关系使用数轴画出来则一目了然,这是本文比一般解答细致的地方,可读性更高。

做过此题之后,才体会到此题确实有难度,虽然做出来不是完全不可能,但是临场考试做出来的可能性确实不大,会耗费很多时间。在此,膜拜一下韦东奕大神!

这个答案比较泛泛而谈,虽然都正确,但有的复杂结论一句话带过,可阅读性不高,因此需要详解。

(0)

相关推荐