第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

中所有的数都同色。

第 3/5 步：情形一：直接套用规则 (ii)

通俗地说

如果第二个点只是第一个点加上一次长度为 $k$ 的跳跃，那么规则 (ii)——把一个数与它减去 $k$ 联系起来——立刻就给出同色的结论。

s=r+k \ \Longrightarrow\ |s-k|=r \ \Longrightarrow\ \text{color}(s)=\text{color}(r)

详细分析

记 $r=r_i$ ， $s=r_{i+1}$ 。若 $s=r+k$ ，则 $|s-k|=r$ ，于是对 $i=s$ 应用染色规则 (ii)（因为在此构造中只有一个下标等于 $k$ ，故 $s\ne k$ 成立），立即得到 $s$ 与 $r=|s-k|$ 同色。