IMO 2024 P1 & P5

听说今年这两道题比较简单，我就来蹭蹭热度了。 P1 是一个不太难的题，但是我很可能把它想复杂了；P5 是一个非常巧妙的 brainteaser 。

P1

求所有实数 \(\alpha\) 满足：对任意正整数 \(n\)，整数 \(\sum\limits_{i=1}^n \lfloor i \alpha \rfloor\) 均为 \(n\) 的倍数。

解答

令 \(S\) 表示所有满足要求的 \(\alpha\) 构成的集合。先来个小观察：如果 \(\alpha \in S\)，那么 \(2 + \alpha \in S\)：对于任何 \(n \in \mathbb{N}^+\)，有 \[\sum_{i=1}^n \lfloor i (\alpha + 2) \rfloor = \sum_{i=1}^n \left( \lfloor i \alpha \rfloor + 2i \right) = \sum_{i=1}^n \lfloor i \alpha \rfloor + n (n + 1)\]

于是我们就只需要研究 \([0, 2)\) 里的 \(\alpha\) 即可。

1. 显然有 \(0 \in S\);
2. 如果 \(0 < \alpha < 1\)，考虑 \(n = \lceil \alpha^{-1} \rceil \geq 2\)，有 \(\sum\limits_{i=1}^n \lfloor i \alpha \rfloor = 1\)，明显不满足要求；
3. 显然有 \(1 \not\in S\)：令 \(n = 2\) 即可。
4. 如果 \(1 < \alpha < 2\):
   1. 如果 \(\alpha \not\in \mathbb{Q}\)，对于任何 \(n \in \mathbb{N}^+\) 有 \(\sum\limits_{i=1}^n \lfloor i (2 - \alpha) \rfloor = \sum\limits_{i=1}^n (2i - 1 - \lfloor i \alpha \rfloor)\) ，故 \(2-\alpha \in S\)，又有 \(0 < 2 - \alpha < 1\)，矛盾。
   2. 如果 \(\alpha \in \mathbb{Q}\)，不妨令 \(\alpha = p / q\) 且 \(gcd(p, q) = 1, q > 1\)。有 \[\sum_{i=1}^{q-1} \left\lfloor i \frac{p}{q} \right \rfloor = \frac{1}{2} \sum_{i=1}^{q-1} \left( \left\lfloor i \frac{p}{q} \right \rfloor + \left\lfloor (q - i) \frac{p}{q} \right \rfloor \right) = \frac{p - 1}{2} (q - 1) \equiv 0 \pmod {q - 1}. \] 可知 \(p\) 为奇数。又考虑 \[\sum_{i=1}^q \left\lfloor i \frac{p}{q} \right \rfloor = p + \frac{1}{2} \sum_{i=1}^q \left\lfloor i \frac{p}{q} \right \rfloor = p + \frac{p - 1}{2} (q - 1) \equiv 0 \pmod{q}. \] 可得 \[\frac{p + 1}{2} \equiv 0 \pmod{q},\] 而这是不可能的，因为 \(0 < \frac{p + 1}{2} < q\).

综上所述，\([0, 2) \cap S = \{0\}\)，故 \(S = \{2k: k \in \mathbb{Z}\}\).

（这个对 \(\alpha \in \mathbb{Q}\) 的讨论好丑好想优化掉……）

P5

憨豆特工在一个 2024 行 2023 列的方格表上做游戏。方格表中恰有 2022 个方格各藏有一个坏人。初始时，憨豆不知道坏人的位置，但是他知道除了第一行和最后一行之外，每行恰有一个坏人，且每列至多有一个坏人。

憨豆想从第一行移动到最后一行，并进行若干轮尝试. 在每一轮尝试中，憨豆可以在第一行中任意选取一个方格出发并不断移动，他每次可以移动到与当前所在方格有公共边的方格内。（他允许移动到之前已经到达过的方格。）若憨豆移动到一个有坏人的方格，则此轮尝试结束，并且他被传送回第一行开始新的一轮尝试。坏人在整个游戏过程中不移动，并且憨豆可以记住每个他经过的方格内是否有坏人。若憨豆到达最后一行的任意一个方格，则游戏结束。

求最小的正整数 \(n\)，使得不论坏人的位置如何分布，憨豆总有策略可以确保他能够经过不超过 \(n\) 轮尝试到达最后一行。

解答

以下给出一个 \(n = 3\) 的构造。所有的图里蓝色为坏人，黄色表示可行路径。

我们先确定第二行的坏人在哪里。这一步直接扫就好了。有两种情况：

1. Case 1：坏人不在第一列或最后一列。如图所示，A 点和 B 点同行，所以至多有一个坏人。不妨设 B 点没坏人，按照黄色路径走即可。
2. Case 2：坏人在第一列或最后一列。不妨设坏人在第一列，那我们便从上到下依次遍历下图的所有绿色方块，遇到第一个坏人就停止。
   1. Case 2-1：我们没有找到任何一个坏人，那么我们可以直接走最后一列即可；
   2. Case 2-2：我们找到了一个坏人，那么按照下面的黄色路径走即可： A 点左上方的点没有坏人是因为 A 点是我们从上往下扫找到的第一个坏人。

至于 \(n\) 为啥不能小于 3：我们就考虑一个 adversarial 的放坏人的方式，

• 第一次探索时我把坏人放在你探索的第一个方块上（在第二行）；
• 第二次探索时我把坏人放在你探索的第一个位于第三行的方块上，这个方块一定和我第一次放坏人的方块不在同一列上，因为你只能从第二行的非坏人方格到第三行。