2021 第 62 届 IMO 第五题详解

引言

问题

两只松鼠

和

为过冬收集了 2021 枚核桃。

将核桃依次编号为 1 到 2021，并在它们最喜欢的树周围挖了一圈共 2021 个小坑。第二天早上，

发现

已经在每个小坑里放入了一枚核桃，但并未注意编号。不开心的

决定用 2021 次操作来改变这些核桃的位置。在第

次操作中，

把与第

号核桃相邻的两枚核桃交换位置。

证明：存在某个

，使得在第

次操作中，

交换了两枚编号为

和

的核桃，且

。

分析

每一次操作之后的状态都具有很大的不确定性，因此我们寻找操作中的某些不变量，进而分析初始状态和终态来找出矛盾。我们将通过染色的方法，来构造这种不变量。下面给出此题的详细解答。

解答

假设命题不成立，那么存在某个 2021 次操作

，使得对任意

，在第

次操作中交换的两个核桃的编号，要么都大于

，要么都小于

。

我们在第

次操作中将第

号核桃染色，我们称染过色的核桃为有色核桃，未染过色的核桃为无色核桃。那么根据题意，染色的顺序是严格从编号 1 依次到编号 2021，那么任何一次操作中，任何无色核桃的编号必然大于任何有色核桃的编号。那么对于操作

而言，任意一次交换的两个核桃必然同时是有色核桃或无色核桃。

我们称连续的若干个有色核桃为一个“串”，即两个端点的有色核桃分别存在某个无色核桃与之相邻，并且任何非端点的有色核桃相邻的两个核桃都是有色核桃。

在操作

中，记第

次操作之后，串数 + 有色核桃数为

。我们证明下面的引理。

引理：对于任意

，

为偶数。

证明：

当

时，即没有操作的初始状态，

为偶数。

假设

为偶数，那么对于第

次操作而言，由于第

号核桃相邻两个核桃同时是有色或无色，交换它们不会改变串数或有色核桃数，而将第

号核桃染色会使有色核桃数 +1。对于串数而言，若相邻两个核桃是无色，则第

号核桃染色之后自身形成一个串，即串数 +1；若相邻的两个核桃是有色，则染色之后要么把相邻两条串连成一条串，要么把除了第

号核桃之外的一整条串破坏掉（这种情况只会在染最后一个核桃的时候发生），也即串数 -1。从而

要么等于

要么等于

，从而

为偶数。由数学归纳法知结论成立。证毕！

我们注意到

是一个奇数，这和引理相矛盾，从而假设不真，即这样的操作

不存在，而原命题成立。

点评

这道题不算很难，难度仅略高于本次 IMO 第一题。如果能够想到用染色的方法，寻找操作之中的不变量，则问题迎刃而解。