给定 $n$ 个正整数，考虑由这 $n$ 个正整数中的一个或多个相加得到的所有的和．求证：这些和可以分成 $n$ 组，且每一组中最大数与最小数之比不大于 $2$．
【难度】
【出处】
无
【标注】
【答案】
略
【解析】
对 $n$ 进行归纳，$n=1$ 时显然．
假设 $n<m$ 时结论都成立，考虑 $n=m$ 的情况．
不妨设给定的正整数为 $a_1\leqslant a_2\leqslant \cdots \leqslant a_m$，并令$$S_i=a_1+a_2+\cdots +a_i,$$其中 $1\leqslant i\leqslant m$．设 $k\in \{1,2,\cdots ,m-1\}$ 是最大的满足 $2S_k\leqslant S_{k+1}$ 的正整数（由 $2S_1=2a_1\leqslant a_1+a_2=S_2$ 知这样的 $k$ 存在），则$$a_{k+1}=S_{k+1}-S_k\geqslant \dfrac 12S_{k+1}\geqslant \dfrac 14S_{k+2}\geqslant \cdots \geqslant \dfrac{1}{2^{m-k}}S_m,$$及 $S_m\leqslant 2^{m-k}a_{k+1}$，因此 $m-k$ 个区间$$\left[a_{k+1},2a_{k+1}\right),\left[2a_{k+1},4a_{k+1}\right),\cdots ,\left[2^{m-k-1}{a_{k+1}},2^{m-k}a_{k+1}\right]$$即可包含所有至少含 $a_{k+1},a_{k+2},\cdots ,a_m$ 之一的一个或多个相加的和，再由归纳假设，$a_1,a_2,\cdots ,a_k$ 中一个或多个的和均可被分成 $k$ 组，故一共可以分为 $m$ 组，即结论对 $n=m$ 也成立，证毕．
假设 $n<m$ 时结论都成立，考虑 $n=m$ 的情况．
不妨设给定的正整数为 $a_1\leqslant a_2\leqslant \cdots \leqslant a_m$，并令$$S_i=a_1+a_2+\cdots +a_i,$$其中 $1\leqslant i\leqslant m$．设 $k\in \{1,2,\cdots ,m-1\}$ 是最大的满足 $2S_k\leqslant S_{k+1}$ 的正整数（由 $2S_1=2a_1\leqslant a_1+a_2=S_2$ 知这样的 $k$ 存在），则$$a_{k+1}=S_{k+1}-S_k\geqslant \dfrac 12S_{k+1}\geqslant \dfrac 14S_{k+2}\geqslant \cdots \geqslant \dfrac{1}{2^{m-k}}S_m,$$及 $S_m\leqslant 2^{m-k}a_{k+1}$，因此 $m-k$ 个区间$$\left[a_{k+1},2a_{k+1}\right),\left[2a_{k+1},4a_{k+1}\right),\cdots ,\left[2^{m-k-1}{a_{k+1}},2^{m-k}a_{k+1}\right]$$即可包含所有至少含 $a_{k+1},a_{k+2},\cdots ,a_m$ 之一的一个或多个相加的和，再由归纳假设，$a_1,a_2,\cdots ,a_k$ 中一个或多个的和均可被分成 $k$ 组，故一共可以分为 $m$ 组，即结论对 $n=m$ 也成立，证毕．
答案
解析
备注
