求具有下列性质的所有正整数 $k$：对任意正整数 $n$，$2^{(k-1)n+1}$ 不整除 $\dfrac{(kn)!}{n!}$．
【难度】
【出处】
2015年全国高中数学联赛（二试）
【标注】
【答案】
$k$ 为 $2^a$，其中 $a=0,1,2,\cdots$
【解析】
对正整数 $m$，设 $v_2(m)$ 表示正整数 $m$ 的标准分解中素因子 $2$ 的方幂，则熟知$$v_2(m!)=m-S(m),$$这里 $S(m)$ 表示正整数 $m$ 在二进制表示下的数码之和．由于 $2^{(k-1)n+1}$ 不整除 $\dfrac{(kn)!}{n!}$ 等价于\[v_2\left(\dfrac{(kn)!}{n!}\right)\leqslant (k-1)n,\]即\[kn-v_2\left((kn)!\right)\geqslant n-v_2\left(n!\right),\]进而本题等价于求所有正整数 $k$，使得 $S(kn)\geqslant S(n)$ 对任意正整数 $n$ 成立．我们证明，所有符合条件的 $k$ 为 $2^a$，其中 $a=0,1,2,\cdots$．一方面，由于 $S\left(2^an\right)=S(n)$ 对任意正整数 $n$ 成立，故 $k=2^a$ 符合条件．另一方面，若 $k$ 不是 $2$ 的方幂，设 $k=2^a\cdot q$，$a\geqslant 0$，$q$ 是大于 $1$ 的奇数．下面构造一个正整数 $n$，使得 $S(kn)<S(n)$．因为\[S(kn)=S\left(2^aqn\right)=S(qn),\]因此问题等价于我们选取的 $q$ 的一个倍数 $m$，使得\[S(m)<S\left(\dfrac{m}{q}\right).\]由 $(2,q)=1$，熟知存在正整数 $u$，使得 $2^u\equiv 1\pmod q$．（事实上，由欧拉定理知，$u$ 可以取 $\varphi(q)$．）设奇数 $q$ 的二进制表示为\[2^{\alpha_1}+2^{\alpha_2}+\cdots+2^{\alpha_t},\]其中 $0=\alpha_1<\alpha_2<\cdots<\alpha_t$，$t\geqslant 2$．取 $m=2^{\alpha_1}+2^{\alpha_2}+\cdots+2^{\alpha_t+tu}$，则 $S(m)=t$，且\[m=q+2^{\alpha_t}\left(2^{tu}-1\right)\equiv 0\pmod q.\]我们有\[\begin{split}\dfrac mq&=1+2^{\alpha_t}\cdot\dfrac{2^{tu}-1}{q}\\&=1+2^{\alpha_t}\cdot\dfrac{2^u-1}{q}\left(1+2^u+\cdots+2^{(t-1)u}\right)\\&=1+\sum_{i=0}^{t-1}\dfrac{2^u-1}{q}\cdot2^{iu+\alpha_t}.\end{split}\]由于 $0<\dfrac{2^u-1}q<2^u$，故正整数 $\dfrac{2^u-1}{q}$ 的二进制表示中的最高次幂小于 $u$，由此可得，对任意整数 $i,j$（$0\leqslant i<j\leqslant t-1$），数 $\dfrac{2^u-1}q\cdot 2^{iu+\alpha_t}$ 与 $\dfrac{2^u-1}q\cdot 2^{ju+\alpha_t}$ 的二进制表示中没有相同的项．又因为 $\alpha_t>0$，故 $\dfrac{2^u-1}q\cdot 2^{iu+\alpha_t}$（$i=0,1,2,\cdots,t-1$）的二进制表示中均不包含 $1$，故\[S\left(\dfrac mq\right)=1+S\left(\dfrac{2^u-1}q\right)\cdot t>t=S(m),\]因此上述选取的 $m$ 满足要求．
综合上述的两个方面可知，所求 $k$ 为 $2^a$，其中 $a=0,1,2,\cdots$．
综合上述的两个方面可知，所求 $k$ 为 $2^a$，其中 $a=0,1,2,\cdots$．
答案
解析
备注
