设 $n$ 与 $k$ 是互素的两个正整数，且 $k<n$，将集合 $M=\{1,2,...,n-1\}$ 中每个数染上蓝，白两色之一，染色法如下：
（1）对 $M$ 中每个 $i$，使 $i$ 和 $n-i$ 同色；
（2）对 $M$ 中每个 $i,i ≠k$，使 $i$ 与 $|k-i|$ 同色．
求证：$M$ 中所有数必为同色．（澳大利亚）
（1）对 $M$ 中每个 $i$，使 $i$ 和 $n-i$ 同色；
（2）对 $M$ 中每个 $i,i ≠k$，使 $i$ 与 $|k-i|$ 同色．
求证：$M$ 中所有数必为同色．（澳大利亚）
【难度】
【出处】
1985年第26届IMO试题
【标注】
【答案】
略
【解析】
设 $lk=nq_l+r_l,l=1,2,\cdots,n-1,1\leqslant r_l\leqslant n-1$．
若 $r_l=r_{l^\prime}$，则 $(l-l^\prime)k=n(q_l-q_{l^\prime})$，因为 $(k,n)=1$，所以 $n|l-l^\prime$．由于 $-n<l-l^\prime<n$，故 $l=l^\prime$．这说明 $l=1,2,\cdots,n-1$ 时，$r_l$ 互不相同．
所以 $M=\{r_1,r_2,\cdots,r_{n-1}\}$．
若 $r_l<n-k$，即 $r_l+k<n$，则 $r_{l+1}=r_l+k$，由题设条件（2），$r_{l+1}$ 与 $r_{l+1}-k=r_l$ 同色．
若 $r_l\leqslant n-k$，即 $r_l+k\geqslant n$，则 $r_{l+1}=r_l+k-n$，于是由题设条件（2），$r_{l+1}$ 与 $k-r_{l+1}=n-r_l$ 同色，再由题设（1）知，$n-r_{l}$ 与 $r_{l}$ 同色，于是 $r_{l+1}$ 与 $r_l$ 同色．
综上所述，$r_{l+1}$ 与 $r_l$ 同色，$l=1,2,\cdots,n-2$，所以 $M$ 中所有数同色．
若 $r_l=r_{l^\prime}$，则 $(l-l^\prime)k=n(q_l-q_{l^\prime})$，因为 $(k,n)=1$，所以 $n|l-l^\prime$．由于 $-n<l-l^\prime<n$，故 $l=l^\prime$．这说明 $l=1,2,\cdots,n-1$ 时，$r_l$ 互不相同．
所以 $M=\{r_1,r_2,\cdots,r_{n-1}\}$．
若 $r_l<n-k$，即 $r_l+k<n$，则 $r_{l+1}=r_l+k$，由题设条件（2），$r_{l+1}$ 与 $r_{l+1}-k=r_l$ 同色．
若 $r_l\leqslant n-k$，即 $r_l+k\geqslant n$，则 $r_{l+1}=r_l+k-n$，于是由题设条件（2），$r_{l+1}$ 与 $k-r_{l+1}=n-r_l$ 同色，再由题设（1）知，$n-r_{l}$ 与 $r_{l}$ 同色，于是 $r_{l+1}$ 与 $r_l$ 同色．
综上所述，$r_{l+1}$ 与 $r_l$ 同色，$l=1,2,\cdots,n-2$，所以 $M$ 中所有数同色．
答案
解析
备注
