据说这道题陶哲轩说他想了7个小时，当年中国队只有北大韦东奕才满分的一届国际奥数比赛题。而这里，给出了一个比较有意思直接的证明方式，里面的思维分析比较有欣赏价值。
50届IMO（俄罗斯提供）：
是一组互不相同的正整数，是有个元素的正整数集合，且不含元素.一只蚱蜢沿着实数轴从0开始向右跳跃步，它跳跃的距离是的某个排列。证明：可以选择一种排列，使得蚱蜢跳跃落下的点所表示的数都不在集合
中。
证明：采用归纳法。
对于,显然成立；
对于,此时，只有一个元素，显然蚱蜢第一次跳跃的距离可以选择不是的元素即可；假设对于的所有结论都成立。现考察
的情况。此时.考虑，。由于的元素只有
个，故一定存在,使得。假设中除之后的正整数序列为,令，显然，。记 集合，则，集合，显然。
① 若中存在两个元素的值是一样的，不妨假设其为，令，由归纳假设，存在的一种排列，可以使得这只蚱蜢跳跃落下的点所表示的数都不在集合中，也不在集合中（因为中也有元素）。在此符合规则的序列下，再跳最后一跳的距离是，此时依然符合规则（因为最后一跳会落入对应数是的点上），故的时候结论也成立；
②中的所有元素的值都是不一样的。若对于任意的,
，由归纳假设知道此时存在的一种排列，使得得这只蚱蜢跳跃落下的点所表示的数都不在集合中，假设这样的排列下对应的落点序列其中一个是（也可能是有且只有一个）。但此时总存在正整数(因为)，有（否则，我们就在那个排列下最后再跳距离为，最后的落点也不在上，从而结论在的时候也成立）。设中最大的元素为，中最大的项为。此时：
②-1：若,则令上述的,令，则由归纳假设，此时存在的一种排列，可以使得这只蚱蜢跳跃落下的点所表示的数都不在集合中，也不在集合中。此时，若存在正整数，有
，则将此等式右边的最后一个替换为,则此时令第
步跳的距离变为。由于是，中最大的项(它们互相不相等)，故，又是中最大的元素，故。之后跳的落点都将比还要大，故都不在中。从而结论在的时候也成立；
②-2：若。我们需注意到一个事实，对任意， 此时存在,有。此时令，序列为中除之后的正整数序列，则此时。由归纳假设可以得知存在的一种排列，可以使得这只蚱蜢跳跃落下的点所表示的数都不在集合中。且此时，这个排列下的最后一跳落下的点是 在 中。此时，将最后一跳的距离 替换为 ，若 ，则替换后跳的落点 。再最后跳的距离是 ,对应的落点是 ，同样也不在 中，故此时结论对也是成立的。否则，上面的过程的 都在 中，则对应 的不同落点有 个（ 遍历 的每个元素），都在 中, 令这些落点对应的数的集合 。这时候，其对应的落点序列（一定有一个，如果有多个，任取其中一个）为，其中 ，而且一定存在相应的正整数 ,有 ，分别表示这只蚱蜢第 次跳的距离是 。现在我们将 和 对调，这样的后果是：① 对调后的落点序列对于 依然满足题设，从而由前面分析可以知道此时结论对也是成立的； ② 对调后的落点在 中，或者对调后的落点不在 中，但此落点之后的落点有在 中的。对于后者，我们注意到，对任意以此 和 的对调，定义 ，显然对任意 ，都有 ，且都不在集合 中。因此对调后的落点一共有 个且它们之间互相不相等。注意到， ，因此至少有两个对调后的落点依然不在 中。令集合合 ， ,
， ，则 。注意到，若存在 ，若对任意 ,均有，则对调之后的落点序列依然对 满足题设，有前面分析知道此时结论对也是成立的。否则，对任意 ，都存在正整数 ，使得 。当注意到，当 的时候， ，从而在 固定下，对任意 ，都有 。注意到 ，故此时一定存在 和 ，有 。令 ，序列 ,有归纳假设，序列 对 满足题设。假设这些落点是 。基于这个落点序列，我们在第 跳（这个落点序列最后一个落点的后面一跳）的距离为 ,此时的落点为 (因为 )，之后再最后一跳的距离为 ，落点为 ，故此时结论对也是成立的。也是成立的。假设，题设是对所有的正整数也是成立的。也是成立的。假设，题设是对所有的正整数都成立。命题得证！都成立。命题得证！个人觉得非常有意思，非常考究学生的思维能力：数学抽象建模能力（个人认为是非常重要的能力），例如前面我的证明过程中对集合的抽象建立。不断分析各种场景（scenario），在现代高科技行业，这种能力是非常重要的，这是一位从事芯片行业的攻城狮的深刻体会。“数学是人类思维的体操”，人要保持健康活力，需要锻炼身体；思维要保持清晰愉悦，也要锻炼思维。
联系客服
