听说今年这两道题比较简单,我就来蹭蹭热度了。 P1 是一个不太难的题,但是我很可能把它想复杂了;P5 是一个非常巧妙的 brainteaser 。
P1
题面
求所有实数 α 满足:对任意正整数 n,整数 i=1∑n⌊iα⌋ 均为 n 的倍数。
解答
令 S 表示所有满足要求的 α 构成的集合。先来个小观察:如果 α∈S,那么 2+α∈S:对于任何 n∈N+,有
∑∗i=1n⌊i(α+2)⌋=∑∗i=1n(⌊iα⌋+2i)=∑_i=1n⌊iα⌋+n(n+1)
于是我们就只需要研究 [0,2) 里的 α 即可。
- 显然有 0∈S;
- 如果 0<α<1,考虑 n=⌈α−1⌉≥2,有 i=1∑n⌊iα⌋=1,明显不满足要求;
- 显然有 1∈S:令 n=2 即可。
- 如果 1<α<2:
- 如果 α∈Q,对于任何 n∈N+ 有 i=1∑n⌊i(2−α)⌋=i=1∑n(2i−1−⌊iα⌋) ,故 2−α∈S> ,又有 0<2−α<1,矛盾。
- 如果 α∈Q,不妨令 α=p/q 且 gcd(p,q)=1,q>1。有
i=1∑q−1⌊iqp⌋=21i=1∑q−1(⌊iqp⌋+⌊(q−i)qp⌋)=>2p−1(q−1)≡0(modq−1).
可知 p 为奇数。又考虑
i=1∑q⌊iqp⌋=p+21i=1∑q⌊iqp⌋=p+2p−1(q−1)≡0(modq).
可得
2p+1≡0(modq),
而这是不可能的,因为 0<2p+1<q.
综上所述,[0,2)∩S={0},故 S={2k:k∈Z}.
(这个对 α∈Q 的讨论好丑好想优化掉……)
P5
题面
憨豆特工在一个 2024 行 2023 列的方格表上做游戏。方格表中恰有 2022 个方格各藏有一个坏人。初始时,憨豆不知道坏人的位置,但是他知道除了第一行和最后一行之外,每行恰有一个坏人,且每列至多有一个坏人。
憨豆想从第一行移动到最后一行,并进行若干轮尝试. 在每一轮尝试中,憨豆可以在第一行中任意选取一个方格出发并不断移动,他每次可以移动到与当前所在方格有公共边的方格内。(他允许移动到之前已经到达过的方格。)若憨豆移动到一个有坏人的方格,则此轮尝试结束,并且他被传送回第一行开始新的一轮尝试。坏人在整个游戏过程中不移动,并且憨豆可以记住每个他经过的方格内是否有坏人。若憨豆到达最后一行的任意一个方格,则游戏结束。
求最小的正整数 n,使得不论坏人的位置如何分布,憨豆总有策略可以确保他能够经过不超过 n 轮尝试到达最后一行。
解答
以下给出一个 n=3 的构造。所有的图里蓝色为坏人,黄色表示可行路径。
我们先确定第二行的坏人在哪里。这一步直接扫就好了。有两种情况:
- Case 1:坏人不在第一列或最后一列。如图所示,A 点和 B 点同行,所以至多有一个坏人。不妨设 B 点没坏人,按照黄色路径走即可。

- Case 2:坏人在第一列或最后一列。不妨设坏人在第一列,那我们便从上到下依次遍历下图的所有绿色方块,遇到第一个坏人就停止。

- Case 2-1:我们没有找到任何一个坏人,那么我们可以直接走最后一列即可;
- Case 2-2:我们找到了一个坏人,那么按照下面的黄色路径走即可:

A 点左上方的点没有坏人是因为 A 点是我们从上往下扫找到的第一个坏人。
至于 n 为啥不能小于 3:我们就考虑一个 adversarial 的放坏人的方式,
- 第一次探索时我把坏人放在你探索的第一个方块上(在第二行);
- 第二次探索时我把坏人放在你探索的第一个位于第三行的方块上,这个方块一定和我第一次放坏人的方块不在同一列上,因为你只能从第二行的非坏人方格到第三行。