证明对于任意一对正整数 $k$ 和 $n$，都存在 $k$ 个（不必不相同的）正整数 $m_{1},m_{2},\ldots,m_{k}$，使得 $1+\dfrac{2^{k}-1}{n}=\left(1+\dfrac{1}{m_{1}}\right)\left(1+\dfrac{1}{m_{2}}\right)\ldots\left(1+\dfrac{1}{m_{k}}\right)$．（日本）
【难度】
【出处】
2013年第54届IMO试题
【标注】
【答案】
略
【解析】
证法一
我们对 $k$ 用数学归纳法．对于 $k=1$，结论是平凡的．下面假设命题对于 $k=j-1$ 成立，我们来证明 $k=j$ 的情形．
情形一：当 $n$ 是奇数时，即有某个正整数 $t$，使得 $n=2t-1$．注意到
$\begin{aligned} 1+\frac{2^{j}-1}{2 t-1} &=\frac{2\left(t+2^{j-1}-1\right)}{2 t} \cdot \frac{2 t}{2 t-1} \\ &=\left(1+\frac{2^{j-1}-1}{t}\right)\left(1+\frac{1}{2 t-1}\right) \end{aligned}$
由归纳假设，我们可以找到 $m_1 ,\ldots ,m_{j-1}$，使得
$
1+\dfrac{2^{j-1}-1}{t}=\left(1+\dfrac{1}{m_{1}}\right)\left(1+\dfrac{1}{m_{2}}\right) \ldots\left(1+\dfrac{1}{m_{j-1}}\right)
$
于是只要取 $m_j =2t-1$ 即可．
情形二：当 $n$ 是偶数时，即有某个正整数 $t$，使得 $n=2t$．这时我们有
$\begin{aligned} 1+\frac{2^{j}-1}{2 t} &=\frac{2 t+2^{j}-1}{2 t+2^{j}-2} \cdot \frac{2 t+2^{i}-2}{2 t} \\ &=\left(1+\frac{1}{2 t+2^{i}-2}\right)\left(1+\frac{2^{j-1}-1}{t}\right) \end{aligned}$
注意到 $2t+2^j -2>0$，以及
$
1+\dfrac{2^{j-1}-1}{t}=\left(1+\dfrac{1}{m_{1}}\right)\left(1+\dfrac{1}{m_{2}}\right) \ldots\left(1+\dfrac{1}{m_{j-1}}\right)
$
我们只要取 $m_{j-1}=2t+2^j -2$ 即可．
证法二
考虑 $n-1$ 和 $-n$ 模 $2^k$ 的余数的二进制展开．
$
n-1 \equiv 2^{a_{1}}+2^{a_{2}}+\ldots+2^{a_r} \left(\bmod 2^{k}\right)
$
其中 $0 \leqslant a_{1}<a_{2}<\ldots<a_{r} \leqslant k-1$．
$
-n \equiv 2^{b_{1}}+2^{b_{2}}+\cdots+2^{b_{s}}\left(\bmod 2^{k}\right)
$
其中 $0 \leqslant b_{1}<b_{2}<\ldots<b_{s} \leqslant k-1$．
因为
$
-1 \equiv 2^{0}+2^{1}+\ldots+2^{k-1}\left(\bmod 2^{k}\right)
$
所以，
$
\left\{a_{1}, a_{2}, \cdots, a_{r}\right\} \bigcup\left\{b_{1}, b_{2}, \cdots, b_{s}\right\}=\{0,1, \cdots, k-1\}
$
且 $r+s=k$．
对于 $1\leqslant p\leqslant r$，$1\leqslant q\leqslant s$，我们记
$\begin{aligned}
S_p &= 2^{a_p}+2^{a_{p+1}}+\ldots+2^{a_r}\\
T_q &= 2^{b_1}+2^{b_2}+\ldots+2^{b_q}
\end{aligned}$
同时规定 $S_{r+1}=T_0 =0$．注意到
$
S_{1}+T_{s}=2^{k}-1
$
以及 $n+T_{s} \equiv 0\left(\bmod 2^{k}\right)$，我们有
$\begin{aligned} 1+\frac{2^{k}-1}{n} &=\frac{n+S_{1}+T_{s}}{n} \\ &=\frac{n+S_{1}+T_{s}}{n+T_{s}} \cdot \frac{n+T_{s}}{n} \\ &=\prod_{p=1}^{r} \frac{n+S_{p}+T_{s}}{n+S_{p+1}+T_{s}} \cdot \prod_{q=1}^{s} \frac{n+T_{q}}{n+T_{q-1}} \\ &=\prod_{p=1}^{r}\left(1+\frac{2^{a_{p}}}{n+S_{p+1}+T_{s}}\right) \cdot \prod_{q=1}^{s}\left(1+\frac{2^{b_{q}}}{n+T_{q-1}}\right) \end{aligned}$
这样，如果我们对于 $1\leqslant p\leqslant r$，$1\leqslant q\leqslant s$，定义
${m_{p}=\dfrac{n+S_{p+1}+T_{s}}{2^{a_p}}} \\ {m_{r+q}=\dfrac{n+T_{q-1}}{2^{b_q}}}
$
就可得到欲证的等式．唯一还需要证明的，是这些 $m_i$ 都是整数．
对于 $1\leqslant p\leqslant r$，我们知道
$
n+S_{p+1}+T_{s} \equiv n+T_{s} \equiv 0\left(\bmod 2^{a_p}\right)
$
对于 $1\leqslant q\leqslant s$，我们有
$
n+T_{q-1} \equiv n+T_{s} \equiv 0\left(\bmod 2^{b_q}\right)
$
即得结论．
证法三
对于任意的 $a$（$\neq 0,-1$），我们都有
$
\left(1+\dfrac{1}{a}\right)\left(1+\dfrac{1}{a+1}\right)=\left(1+\dfrac{1}{\dfrac{a}{2}}\right)
$
我们可以把题目中要求的分数写成下述形式：
$\begin{aligned}
\frac{n+2^{k}-1}{n}=\frac{n+1}{n} \cdot \frac{n+2}{n+1} \cdot \frac{n+3}{n+2} \cdot \ldots \cdot \frac{n+2^{k}-2}{n+2^{k}-3} \cdot \frac{n+2^{k}-1}{n+2^{k}-2}
\end{aligned}$
并注意到在等式右边有 $2^k -1$ 个分数．
现在我们根据 $n$ 的奇偶性把等式右边的分数两两配对．当 $n$ 是偶数时上式可以写成
$\begin{aligned}
\left(\frac{n+1}{n} \cdot \frac{n+2}{n+1}\right)\left(\frac{n+3}{n+2} \cdot \frac{n+4}{n+3}\right) \ldots\left(\frac{n+2^{k}-3}{n+2^{k}-4} \cdot \frac{n+2^{k}-2}{n+2^{k}-3}\right) \frac{n+2^{k}-1}{n+2^{k}-2}
\end{aligned}$
从而得到
$
\left(\dfrac{\frac{n}{2}+1}{\frac{n}{2}} \cdot \dfrac{\frac{n}{2}+2}{\frac{n}{2}+1} \cdots \dfrac{\frac{n}{2}+2^{k-1}-1}{\frac{n}{2}+2^{k-1}-2}\right) \dfrac{n+2^{k}-1}{n+2^{k}-2}
$ ①
这样括号内的 $2^{k-1}-1$ 个分数和最后一个分数都具有我们想要的形式．
当 $n$ 是奇数时上式可以写成
$\begin{aligned}
\frac{n+1}{n}\left(\frac{n+2}{n+1} \cdot \frac{n+3}{n+2}\right)\left(\frac{n+4}{n+3}\cdot \frac{n+5}{n+4}\right) \ldots\left(\frac{n+2^{k}-2}{n+2^{k}-3} \cdot \frac{n+2^{k}-1}{n+2^{k}-2}\right)
\end{aligned}$
从而得到
$\dfrac{n+1}{n}\left(\dfrac{\frac{n+1}{2}+1}{\frac{n+1}{2}} \cdot \dfrac{\frac{n+1}{2}+2}{\frac{n+1}{2}+1} \cdots \dfrac{\frac{n+1}{2}+2^{k-1}-2}{\frac{n+1}{2}+2^{k-1}-3} \cdot \dfrac{\frac{n+1}{2}+2^{k-1}-1}{\frac{n+1}{2}+2^{k-1}-2}\right)
$ ②
这样括号内的 $2^{k-1}-1$ 个分数和最前面的一个分数都具有我们想要的形式．
我们可以对表达式 ① 和 ② 中括号内的分数重复上述操作．在第 $j$（$=1,2,\ldots$）次操作时，分数的总数由 $2^{k-j+1}+j-2$ 变成 $2^{k-j}+j-1$，这样只要重复 $k$ 次，即可达到命题所求．
我们对 $k$ 用数学归纳法．对于 $k=1$，结论是平凡的．下面假设命题对于 $k=j-1$ 成立，我们来证明 $k=j$ 的情形．
情形一：当 $n$ 是奇数时，即有某个正整数 $t$，使得 $n=2t-1$．注意到
$\begin{aligned} 1+\frac{2^{j}-1}{2 t-1} &=\frac{2\left(t+2^{j-1}-1\right)}{2 t} \cdot \frac{2 t}{2 t-1} \\ &=\left(1+\frac{2^{j-1}-1}{t}\right)\left(1+\frac{1}{2 t-1}\right) \end{aligned}$
由归纳假设，我们可以找到 $m_1 ,\ldots ,m_{j-1}$，使得
$
1+\dfrac{2^{j-1}-1}{t}=\left(1+\dfrac{1}{m_{1}}\right)\left(1+\dfrac{1}{m_{2}}\right) \ldots\left(1+\dfrac{1}{m_{j-1}}\right)
$
于是只要取 $m_j =2t-1$ 即可．
情形二：当 $n$ 是偶数时，即有某个正整数 $t$，使得 $n=2t$．这时我们有
$\begin{aligned} 1+\frac{2^{j}-1}{2 t} &=\frac{2 t+2^{j}-1}{2 t+2^{j}-2} \cdot \frac{2 t+2^{i}-2}{2 t} \\ &=\left(1+\frac{1}{2 t+2^{i}-2}\right)\left(1+\frac{2^{j-1}-1}{t}\right) \end{aligned}$
注意到 $2t+2^j -2>0$，以及
$
1+\dfrac{2^{j-1}-1}{t}=\left(1+\dfrac{1}{m_{1}}\right)\left(1+\dfrac{1}{m_{2}}\right) \ldots\left(1+\dfrac{1}{m_{j-1}}\right)
$
我们只要取 $m_{j-1}=2t+2^j -2$ 即可．
证法二
考虑 $n-1$ 和 $-n$ 模 $2^k$ 的余数的二进制展开．
$
n-1 \equiv 2^{a_{1}}+2^{a_{2}}+\ldots+2^{a_r} \left(\bmod 2^{k}\right)
$
其中 $0 \leqslant a_{1}<a_{2}<\ldots<a_{r} \leqslant k-1$．
$
-n \equiv 2^{b_{1}}+2^{b_{2}}+\cdots+2^{b_{s}}\left(\bmod 2^{k}\right)
$
其中 $0 \leqslant b_{1}<b_{2}<\ldots<b_{s} \leqslant k-1$．
因为
$
-1 \equiv 2^{0}+2^{1}+\ldots+2^{k-1}\left(\bmod 2^{k}\right)
$
所以，
$
\left\{a_{1}, a_{2}, \cdots, a_{r}\right\} \bigcup\left\{b_{1}, b_{2}, \cdots, b_{s}\right\}=\{0,1, \cdots, k-1\}
$
且 $r+s=k$．
对于 $1\leqslant p\leqslant r$，$1\leqslant q\leqslant s$，我们记
$\begin{aligned}
S_p &= 2^{a_p}+2^{a_{p+1}}+\ldots+2^{a_r}\\
T_q &= 2^{b_1}+2^{b_2}+\ldots+2^{b_q}
\end{aligned}$
同时规定 $S_{r+1}=T_0 =0$．注意到
$
S_{1}+T_{s}=2^{k}-1
$
以及 $n+T_{s} \equiv 0\left(\bmod 2^{k}\right)$，我们有
$\begin{aligned} 1+\frac{2^{k}-1}{n} &=\frac{n+S_{1}+T_{s}}{n} \\ &=\frac{n+S_{1}+T_{s}}{n+T_{s}} \cdot \frac{n+T_{s}}{n} \\ &=\prod_{p=1}^{r} \frac{n+S_{p}+T_{s}}{n+S_{p+1}+T_{s}} \cdot \prod_{q=1}^{s} \frac{n+T_{q}}{n+T_{q-1}} \\ &=\prod_{p=1}^{r}\left(1+\frac{2^{a_{p}}}{n+S_{p+1}+T_{s}}\right) \cdot \prod_{q=1}^{s}\left(1+\frac{2^{b_{q}}}{n+T_{q-1}}\right) \end{aligned}$
这样，如果我们对于 $1\leqslant p\leqslant r$，$1\leqslant q\leqslant s$，定义
${m_{p}=\dfrac{n+S_{p+1}+T_{s}}{2^{a_p}}} \\ {m_{r+q}=\dfrac{n+T_{q-1}}{2^{b_q}}}
$
就可得到欲证的等式．唯一还需要证明的，是这些 $m_i$ 都是整数．
对于 $1\leqslant p\leqslant r$，我们知道
$
n+S_{p+1}+T_{s} \equiv n+T_{s} \equiv 0\left(\bmod 2^{a_p}\right)
$
对于 $1\leqslant q\leqslant s$，我们有
$
n+T_{q-1} \equiv n+T_{s} \equiv 0\left(\bmod 2^{b_q}\right)
$
即得结论．
证法三
对于任意的 $a$（$\neq 0,-1$），我们都有
$
\left(1+\dfrac{1}{a}\right)\left(1+\dfrac{1}{a+1}\right)=\left(1+\dfrac{1}{\dfrac{a}{2}}\right)
$
我们可以把题目中要求的分数写成下述形式：
$\begin{aligned}
\frac{n+2^{k}-1}{n}=\frac{n+1}{n} \cdot \frac{n+2}{n+1} \cdot \frac{n+3}{n+2} \cdot \ldots \cdot \frac{n+2^{k}-2}{n+2^{k}-3} \cdot \frac{n+2^{k}-1}{n+2^{k}-2}
\end{aligned}$
并注意到在等式右边有 $2^k -1$ 个分数．
现在我们根据 $n$ 的奇偶性把等式右边的分数两两配对．当 $n$ 是偶数时上式可以写成
$\begin{aligned}
\left(\frac{n+1}{n} \cdot \frac{n+2}{n+1}\right)\left(\frac{n+3}{n+2} \cdot \frac{n+4}{n+3}\right) \ldots\left(\frac{n+2^{k}-3}{n+2^{k}-4} \cdot \frac{n+2^{k}-2}{n+2^{k}-3}\right) \frac{n+2^{k}-1}{n+2^{k}-2}
\end{aligned}$
从而得到
$
\left(\dfrac{\frac{n}{2}+1}{\frac{n}{2}} \cdot \dfrac{\frac{n}{2}+2}{\frac{n}{2}+1} \cdots \dfrac{\frac{n}{2}+2^{k-1}-1}{\frac{n}{2}+2^{k-1}-2}\right) \dfrac{n+2^{k}-1}{n+2^{k}-2}
$ ①
这样括号内的 $2^{k-1}-1$ 个分数和最后一个分数都具有我们想要的形式．
当 $n$ 是奇数时上式可以写成
$\begin{aligned}
\frac{n+1}{n}\left(\frac{n+2}{n+1} \cdot \frac{n+3}{n+2}\right)\left(\frac{n+4}{n+3}\cdot \frac{n+5}{n+4}\right) \ldots\left(\frac{n+2^{k}-2}{n+2^{k}-3} \cdot \frac{n+2^{k}-1}{n+2^{k}-2}\right)
\end{aligned}$
从而得到
$\dfrac{n+1}{n}\left(\dfrac{\frac{n+1}{2}+1}{\frac{n+1}{2}} \cdot \dfrac{\frac{n+1}{2}+2}{\frac{n+1}{2}+1} \cdots \dfrac{\frac{n+1}{2}+2^{k-1}-2}{\frac{n+1}{2}+2^{k-1}-3} \cdot \dfrac{\frac{n+1}{2}+2^{k-1}-1}{\frac{n+1}{2}+2^{k-1}-2}\right)
$ ②
这样括号内的 $2^{k-1}-1$ 个分数和最前面的一个分数都具有我们想要的形式．
我们可以对表达式 ① 和 ② 中括号内的分数重复上述操作．在第 $j$（$=1,2,\ldots$）次操作时，分数的总数由 $2^{k-j+1}+j-2$ 变成 $2^{k-j}+j-1$，这样只要重复 $k$ 次，即可达到命题所求．
答案
解析
备注
