设 $n$ 是大于 $1$ 的奇数，已给 $x_{0}=\left(x_{1}^{(0)}, x_{2}^{(0)}, x_{n}^{(0)}\right)=(1,0, \cdots, 0,1)$ 设 $x_{i}^{k}=\left\{\begin{array}{l}{0, x_{i}^{(k-1)}=x_{i+1}^{k-1}} \\ {1, x_{i}^{(k-1)} \neq x_{i+1}^{k-1}, i=1,2, \cdots, n}\end{array}\right.$ 其中 $x_{n+1}^{k-1}=x_{1}^{k-1}$，记 $x_{k}=\left(x_{1}^{(k)}, x_{2}^{(k)}, \cdots, x_{n}^{(k)}\right), k=1,2, \cdots$ 若正整数 $m$ 满足 $x_{m}=x_{0}$，求证 $m$ 是 $n$ 的倍数．
【难度】
【出处】
1995第10届CMO试题
【标注】
【答案】
略
【解析】
$x_{i}^{(k)}=x_{i}^{(k-1)}+x_{i+1}^{(k-1)}$，故由归纳法易得 $x_{i}^{(k)}=\sum_{i=0}^{k} C_{k}^{i} x_{i+t}^{(0)}(\bmod 2)$
为简洁计，以下推导中省去 $\mod 2$，并记 $x_{i+t}^{(0)}=x_{i+t}$．
若 $m$ 不是 $n$ 的倍数，则 $m=q n+r, 0<r<n$，记
$a_{i}=\left\{\begin{array}{l}{C_{m}^{i}+C_{m}^{i+n}+\cdots+C_{m}^{i+q n}, 1 \leqslant i \leqslant r} \\ {C_{m}^{i}+C_{m}^{i+n}+\cdots+C_{m}^{i+(q-1)} \cdot r<i}\end{array}\right.$
则 $x_{i}^{(m)}=x_{i}+a_{1} x_{i+1}+a_{2} x_{i+2}+\cdots+a_{n} x_{i+n}$ 故 $a_{1} x_{i+1}+a_{2} x_{i+2}+\cdots+a_{n} x_{i+n}=0$
令 $i=1,2, \cdots, n$，即有 $a_{n-1}+a_{n}=0, a_{n-2}+a_{n-1}=0, \cdots, a_{1}+a_{n}=0$ 故 $a_{1}, a_{2}, \cdots, a_{n}$ 奇偶性完全相同．而另一方面
$a_{r}=C_{m}^{r}+C_{m}^{r+n}+\cdots+C_{m}^{r+q n}=C_{m}^{m-r}+C_{m}^{m-r-n}+\cdots+C_{m}^{m-r-q n}\\=C_{n}^{q n}+C_{m}^{(q-1)_{n}}+\cdots+C_{m}^{n}+1=a_{n}+1$
得出 $a_r$ 与 $a_n$ 的奇偶性不同，矛盾．故 $m$ 一定为 $n$ 的倍数．
为简洁计，以下推导中省去 $\mod 2$，并记 $x_{i+t}^{(0)}=x_{i+t}$．
若 $m$ 不是 $n$ 的倍数，则 $m=q n+r, 0<r<n$，记
$a_{i}=\left\{\begin{array}{l}{C_{m}^{i}+C_{m}^{i+n}+\cdots+C_{m}^{i+q n}, 1 \leqslant i \leqslant r} \\ {C_{m}^{i}+C_{m}^{i+n}+\cdots+C_{m}^{i+(q-1)} \cdot r<i}\end{array}\right.$
则 $x_{i}^{(m)}=x_{i}+a_{1} x_{i+1}+a_{2} x_{i+2}+\cdots+a_{n} x_{i+n}$ 故 $a_{1} x_{i+1}+a_{2} x_{i+2}+\cdots+a_{n} x_{i+n}=0$
令 $i=1,2, \cdots, n$，即有 $a_{n-1}+a_{n}=0, a_{n-2}+a_{n-1}=0, \cdots, a_{1}+a_{n}=0$ 故 $a_{1}, a_{2}, \cdots, a_{n}$ 奇偶性完全相同．而另一方面
$a_{r}=C_{m}^{r}+C_{m}^{r+n}+\cdots+C_{m}^{r+q n}=C_{m}^{m-r}+C_{m}^{m-r-n}+\cdots+C_{m}^{m-r-q n}\\=C_{n}^{q n}+C_{m}^{(q-1)_{n}}+\cdots+C_{m}^{n}+1=a_{n}+1$
得出 $a_r$ 与 $a_n$ 的奇偶性不同，矛盾．故 $m$ 一定为 $n$ 的倍数．
答案
解析
备注
