IMO 2024 P1 & P5

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

P1

题面

求所有实数 α\alpha 满足:对任意正整数 nn,整数 i=1niα\sum\limits_{i=1}^n \lfloor i \alpha \rfloor 均为 nn 的倍数。

解答

SS 表示所有满足要求的 α\alpha 构成的集合。先来个小观察:如果 αS\alpha \in S,那么 2+αS2 + \alpha \in S:对于任何 nN+n \in \mathbb{N}^+,有

i=1ni(α+2)=i=1n(iα+2i)=_i=1niα+n(n+1)\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)[0, 2) 里的 α\alpha 即可。

  1. 显然有 0S0 \in S;
  2. 如果 0<α<10 < \alpha < 1,考虑 n=α12n = \lceil \alpha^{-1} \rceil \geq 2,有 i=1niα=1\sum\limits_{i=1}^n \lfloor i \alpha \rfloor = 1,明显不满足要求;
  3. 显然有 1∉S1 \not\in S:令 n=2n = 2 即可。
  4. 如果 1<α<21 < \alpha < 2:
    1. 如果 α∉Q\alpha \not\in \mathbb{Q},对于任何 nN+n \in \mathbb{N}^+i=1ni(2α)=i=1n(2i1iα)\sum\limits_{i=1}^n \lfloor i (2 - \alpha) \rfloor = \sum\limits_{i=1}^n (2i - 1 - \lfloor i \alpha \rfloor) ,故 2αS2-\alpha \in S> ,又有 0<2α<10 < 2 - \alpha < 1,矛盾。
    2. 如果 αQ\alpha \in \mathbb{Q},不妨令 α=p/q\alpha = p / qgcd(p,q)=1,q>1gcd(p, q) = 1, q > 1。有 i=1q1ipq=12i=1q1(ipq+(qi)pq)=>p12(q1)0(modq1).\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}. 可知 pp 为奇数。又考虑 i=1qipq=p+12i=1qipq=p+p12(q1)0(modq).\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}. 可得 p+120(modq),\frac{p + 1}{2} \equiv 0 \pmod{q}, 而这是不可能的,因为 0<p+12<q0 < \frac{p + 1}{2} < q.

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

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

P5

题面

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

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

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

解答

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

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

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

至于 nn 为啥不能小于 3:我们就考虑一个 adversarial 的放坏人的方式,

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