定义 $n$ 元整数组的一次变换为：$\left(a_{1}, a_{2}, \cdots, a_{n-1}, a_{n}\right) \rightarrow\left(a_{1}+a_{2}, a_{2}+a_{3}, \cdots, a_{n-1}+a_{n}, a_{n}+a_{1}\right)$．求所有的正整数对 $(n,k)(n,k\geqslant 2)$，满足：对任意的 $n$ 元整数组 $\left(a_{1}, a_{2}, \cdots, a_{n}\right)$，在有限次变换后所得数组中每一个数都是 $k$ 的倍数．
【难度】
【出处】
2016年中国西部数学邀请赛试题
【标注】
【答案】
略
【解析】
$(n, k)=\left(2^{p}, 2^{q}\right), p, q \in \mathbf{N}_{+}$．
引理：记 $n$ 元整数组 $\left(a_{1}, a_{2}, \cdots, a_{n}\right)$ 经过 $t$ 次变换后所得的数组为 $\left(a_{1}^{(t)}, a_{2}^{(t)}, \cdots, a_{n}^{(t)}\right)$，则 $a_{i}^{(t)}=a_{i} C_{t}^{0}+a_{i+1} C_{t}^{1}+\cdots+a_{i+t} C_{t}^{t}, i=1,2, \cdots, n$
引理的证明：用数学归纳法．
当 $t= 1$ 时结论显然成立．
设 $a_{i}^{(t)}=a_{i} C_{t}^{0}+a_{i+1} C_{t}^{1}+\cdots+a_{i+t} C_{t}^{t}, i=1,2, \cdots, n$．
则 $a_{i}^{(t+1)}=a_{i}^{(t)}+a_{i+1}^{(t+1)}=\left(a_{i} C_{t}^{0}+a_{i+1} C_{t}^{1}+\cdots+a_{i+t} C_{t}^{t}\right)+\left(a_{i+1} C_{t}^{0}+a_{i+2} C_{t}^{1}+\cdots+a_{i+1+t} C_{t}^{t}\right)$
$=a_iC_t^0+a_{i+1}(C_t^1+C_t^0)+a_{i+2}(C_t^2+C_t^1)+\cdots+a_{i+t}(C_t^t+C_t^{t-1})+a_{i+1+t}C^t_t$
$=a_iC^0_{t+1}+a_{i+1}C^1_{t+1}+\cdots+a_{i+t+1}C^{t+1}_{t+1}$
引理证毕，回到原题
一方面，我们证明 $n、k$ 均为 $2$ 的幂．
注意到每次变换后所得的 $n$ 个数之和为原 $n$ 个数之和的 $2$ 倍．
令 $a_{1}=1, a_{2}=a_{3}=\cdots=a_{n}=0$．
由题设知经过有限次（不妨设为 $m$ 次）变换后所得的每个数均为 $k$ 的倍数，由前可知 $m$ 次变换后所得的 $n$ 个数之和为 $2^m$，故 $k|2^m$，即 $k$ 为 $2$ 的幂．
于是，$m$ 次变换后所得的每个数均为 $2$ 的倍数，进而以后的每次变换后 所得的数均为 $2$ 的倍数．
取 $2^{s}>m, s \in \mathbf{N}_{+}$．
注意到 $C_{2^s}^{i}=\dfrac{2^{s}}{i} C_{2^{s}-1}^{i-1}\left(1 \leqslant i \leqslant 2^{s}-1\right)$ 为偶数．①
则经过 $2^s$ 次变换后有 $a_{1}^{\left(2^{s}\right)} \equiv a_{1}+a_{1+2^s} \equiv 0(\bmod 2)$，故 $a_{1+2^s}=1=a_{1}$，于是，即 $n| 2^s$，于是 $n$ 为 $2$ 的幂．另一方面，我们说明当 $(n, k)=\left(2^{p}, 2^{q}\right), p, q \in \mathbf{N}_{+}$ 时，任意 $n$ 元整数组 $\left(a_{1}, a_{2}, \cdots, a_{n}\right)$ 均能经过有限次变换后使得到的每个数均为 $k$ 的倍数．
结合引理 ①，对数组 $\left(a_{1}, a_{2}, \cdots, a_{n}\right)$ 经过 $n=2^p$ 次变换后，有 $a_{i}^{(n)} \equiv a_{i}+a_{i+n} \equiv 0(\bmod 2), i=1,2, \cdots, n$．
再将 $\left(\dfrac{1}{2} a_{1}^{(n)}, \dfrac{1}{2} a_{2}^{(n)}, \cdots, \dfrac{1}{2} a_{n}^{(n)}\right)$ 经过 $n=2^p$ 次变换得到的每个数也均为偶数，即 $a_{i}^{(2 n)} \equiv 0(\bmod 4), i=1 \cdot 2, \cdots, n$．
由归纳原理知 $a_{i}^{(qn)} \equiv 0\left(\bmod 2^{q}\right), i=1,2, \cdots, n$，即每个数均为 $k=2^{q}$ 的倍数．
综上，结论成立．
引理：记 $n$ 元整数组 $\left(a_{1}, a_{2}, \cdots, a_{n}\right)$ 经过 $t$ 次变换后所得的数组为 $\left(a_{1}^{(t)}, a_{2}^{(t)}, \cdots, a_{n}^{(t)}\right)$，则 $a_{i}^{(t)}=a_{i} C_{t}^{0}+a_{i+1} C_{t}^{1}+\cdots+a_{i+t} C_{t}^{t}, i=1,2, \cdots, n$
引理的证明：用数学归纳法．
当 $t= 1$ 时结论显然成立．
设 $a_{i}^{(t)}=a_{i} C_{t}^{0}+a_{i+1} C_{t}^{1}+\cdots+a_{i+t} C_{t}^{t}, i=1,2, \cdots, n$．
则 $a_{i}^{(t+1)}=a_{i}^{(t)}+a_{i+1}^{(t+1)}=\left(a_{i} C_{t}^{0}+a_{i+1} C_{t}^{1}+\cdots+a_{i+t} C_{t}^{t}\right)+\left(a_{i+1} C_{t}^{0}+a_{i+2} C_{t}^{1}+\cdots+a_{i+1+t} C_{t}^{t}\right)$
$=a_iC_t^0+a_{i+1}(C_t^1+C_t^0)+a_{i+2}(C_t^2+C_t^1)+\cdots+a_{i+t}(C_t^t+C_t^{t-1})+a_{i+1+t}C^t_t$
$=a_iC^0_{t+1}+a_{i+1}C^1_{t+1}+\cdots+a_{i+t+1}C^{t+1}_{t+1}$
引理证毕，回到原题
一方面，我们证明 $n、k$ 均为 $2$ 的幂．
注意到每次变换后所得的 $n$ 个数之和为原 $n$ 个数之和的 $2$ 倍．
令 $a_{1}=1, a_{2}=a_{3}=\cdots=a_{n}=0$．
由题设知经过有限次（不妨设为 $m$ 次）变换后所得的每个数均为 $k$ 的倍数，由前可知 $m$ 次变换后所得的 $n$ 个数之和为 $2^m$，故 $k|2^m$，即 $k$ 为 $2$ 的幂．
于是，$m$ 次变换后所得的每个数均为 $2$ 的倍数，进而以后的每次变换后 所得的数均为 $2$ 的倍数．
取 $2^{s}>m, s \in \mathbf{N}_{+}$．
注意到 $C_{2^s}^{i}=\dfrac{2^{s}}{i} C_{2^{s}-1}^{i-1}\left(1 \leqslant i \leqslant 2^{s}-1\right)$ 为偶数．①
则经过 $2^s$ 次变换后有 $a_{1}^{\left(2^{s}\right)} \equiv a_{1}+a_{1+2^s} \equiv 0(\bmod 2)$，故 $a_{1+2^s}=1=a_{1}$，于是，即 $n| 2^s$，于是 $n$ 为 $2$ 的幂．另一方面，我们说明当 $(n, k)=\left(2^{p}, 2^{q}\right), p, q \in \mathbf{N}_{+}$ 时，任意 $n$ 元整数组 $\left(a_{1}, a_{2}, \cdots, a_{n}\right)$ 均能经过有限次变换后使得到的每个数均为 $k$ 的倍数．
结合引理 ①，对数组 $\left(a_{1}, a_{2}, \cdots, a_{n}\right)$ 经过 $n=2^p$ 次变换后，有 $a_{i}^{(n)} \equiv a_{i}+a_{i+n} \equiv 0(\bmod 2), i=1,2, \cdots, n$．
再将 $\left(\dfrac{1}{2} a_{1}^{(n)}, \dfrac{1}{2} a_{2}^{(n)}, \cdots, \dfrac{1}{2} a_{n}^{(n)}\right)$ 经过 $n=2^p$ 次变换得到的每个数也均为偶数，即 $a_{i}^{(2 n)} \equiv 0(\bmod 4), i=1 \cdot 2, \cdots, n$．
由归纳原理知 $a_{i}^{(qn)} \equiv 0\left(\bmod 2^{q}\right), i=1,2, \cdots, n$，即每个数均为 $k=2^{q}$ 的倍数．
综上，结论成立．
答案
解析
备注
