第2题

设

n

与

k

是互质的正整数，且

k < n

。将集合

M = \{1, 2, \ldots, n-1\}

中每个数染成蓝色或白色，满足：(i) 对每个

i \in M

，

i

与

n-i

同色；(ii) 对每个满足

i \ne k

的

i \in M

，

i

与

|i-k|

同色。证明

M

中所有的数都同色。

第 2/5 步：相邻剩余之差的两种情形

通俗地说

在剩余组成的圆环上从一个标记点走到下一个，每一步都是长度为 $k$ 的跳跃——只是一旦越过圆环顶端（值 $n$ ），落点就比直接相加低了整整 $n$ 。

r_{i+1} = r_i + k \quad\text{or}\quad r_{i+1} = r_i + k - n

详细分析

根据定义 $r_{i+1}-r_i \equiv k \pmod n$ ，又因 $r_i,r_{i+1}\in\{1,\dots,n-1\}$ ，实际（非模意义下）的差要么恰为 $k$ ，要么为 $k-n$ （当加上 $k$ 超过 $n$ 而发生“绕圈”时）。