求具有下述性质的所有正整数 $k$:对任意正整数 $n$,$2^{(k-1)n+1}$ 不整除 $\dfrac{(kn)!}{n!}$.
【难度】
【出处】
【标注】
【答案】
$2^a$($a=0,1,2\cdots$)
【解析】
对正整数 $m$,设 $v_2(m)$ 表示正整数 $m$ 的标准分解中素因子 $2$ 的方幂,则熟知$$v_2(m!)=m-S(m)\qquad\cdots\cdots\text{ ① }$$这里 $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[(kn)!]\geqslant n-v_2(n!),$$进而由 $\text{ ① }$ 知,本题等价于求所有正整数 $k$,使得 $S(kn)\geqslant S(n)$ 对任意正整数 $n$ 成立.
我们证明,所有符合条件的 $k$ 为 $2^a$($a=0,1,2,\cdots$).
一方面,由于 $S(2^an)=S(n)$ 对任意正整数 $n$ 成立,故 $k=2^a$ 符合条件.
另一方面,若 $k$ 不是 $2$ 的方幂,设 $k=2^a\cdot q,a\geqslant0$,$q$ 是大于 $1$ 的奇数.
下面构造一个正整数 $n$,使得 $S(kn)<S(n)$,因为$$S(kn)=S(2^aqn)=S(qn),$$因此问题等价于我们选取 $q$ 的一个倍数 $m$,使得$$S(m)<S\left(\dfrac{m}{q}\right).$$由于 $(2,q)=1$,熟知存在正整数 $u$,使得 $2^u\equiv1\pmod{q}$.
设奇数 $q$ 的二进制表示为$$2^{\alpha_1}+2^{\alpha_2}+\cdots+2^{\alpha_t},0=\alpha_1<\alpha_2<\cdots<\alpha_t,t\geqslant2.$$取 $m=2^{\alpha_1}+2^{\alpha_2}+\cdots+2^{\alpha_{t-1}}+2^{\alpha_{t-1}+tu}$,则$$S(m)=t,\land m=q+2^{\alpha_t}(2^{tu}-1)\equiv0\pmod{q}.$$我们有\[\begin{split}\dfrac{m}{q}&=1+2^{\alpha_t}\cdot\dfrac{2^{tu}-1}{q}\\&=1+2^{\alpha_t}\cdot\dfrac{2^{tu}-1}{q}(1+2^u+\cdots+2^{(t-1)u})\\&=1+\sum\limits_{t=0}^{t-1}{\dfrac{2^u-1}{q}\cdot2^{lu+\alpha_t}}\qquad\cdots\cdots\text{ ② }.\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}\cdot2^{iu+\alpha_t}$ 与 $\dfrac{2^u-1}{q}\cdot2^{ju+\alpha_t}$ 的二进制表示中没有相同的项.
又因为 $\alpha_t>0$,故 $\dfrac{2^u-1}{q}\cdot2^{lu+\alpha_t}$ 的二进制表示中均不包含 $1$,故由 $\text{ ② }$ 可知$$S\left(\dfrac{m}{q}\right)=1+S\left(\dfrac{2^u-1}{q}\right)\cdot t>t=S(m).$$因此上述选取的 $m$ 满足要求.
综合上述的两方面可知,所求的 $k$ 为 $2^a$($a=0,1,2\cdots$).
答案 解析 备注
0.111908s