对每一个正整数 $n$，开普敦银行都发行面值为 $\dfrac{1}{n}$ 的硬币．给定总额不超过 $99+\dfrac{1}{2}$ 的有限多个这样的硬币（面值不必两两不同），证明可以把它们分为至多 $100$ 组，使得每一组中硬币的面值之和最多是 $1$．（卢森堡）
【难度】
【出处】
2014年第55届IMO试题
【标注】
【答案】
略
【解析】
我们将证明一般性的结论：对任意正整数 $N$，给定总额不超过 $N-\dfrac{1}{2}$ 的有限多个这样的硬币，总可以把它们分为至多 $N$ 组，使得每一组中硬币的面值之和最多是 $1$．
如果一些硬币的面值之和具有 $\dfrac{1}{k}$（$k$ 是正整数）的形式，则我们将这些硬币合并为一枚硬币．如果合并之后的硬币可以按要求分组，则初始时的硬币同样可以按要求分组．
由于在合并过程中硬币的数量是单调递减的，所以到某个时刻没有更多的合并操作可以进行了．此时，对于每个偶数 $k$，最多有一枚硬币面值为 $\dfrac{1}{k}$（否则两枚这样的硬币可以被合并）；对于每个奇数 $k>1$，最多有 $(k-1)$ 枚硬币面值为 $\dfrac{1}{k}$（否则 $k$ 枚这样的硬币可以被合并）．
在此情况下，先将所有面值为 $1$ 的硬币分别编为一组．如果有 $d$ 枚这样的硬币，则可以去除这样的硬币并在问题中用 $N-d$ 来代替 $N$．因此我们不妨假设此时没有面值为 $1$ 的硬币．
我们按如下方式将硬币进行分组．对于 $1,2,\ldots,N$ 中的每个正整数，将所有面值为 $\dfrac{1}{2k-1}$ 和 $\dfrac{1}{2k-2}$ 的硬币放入第 $k$ 组，则第 $k$ 组中所有硬币的面值之和不超过
$
(2 k-2) \cdot \dfrac{1}{2 k-1}+\dfrac{1}{2 k}<1
$
然后再考虑所有面值小于 $\frac{1}{2N}$ 的硬币，将它们依次放入各组当中．每次选择一枚这样的硬币，必有某一组中硬市的面值之和不超过 $1-\dfrac{1}{2N}$（否则各组硬币的面值总和将大于 $N(1-\dfrac{1}{2N})=N-\dfrac{1}{2}$，与已知条件矛盾），那么就将这样小面值的硬币放入该组中，则该组硬币的面值之和不超过 $1$．重复这样的操作，我们就把所有的硬币按要求分成了至多 $N$ 组．证毕!
如果一些硬币的面值之和具有 $\dfrac{1}{k}$（$k$ 是正整数）的形式，则我们将这些硬币合并为一枚硬币．如果合并之后的硬币可以按要求分组，则初始时的硬币同样可以按要求分组．
由于在合并过程中硬币的数量是单调递减的，所以到某个时刻没有更多的合并操作可以进行了．此时，对于每个偶数 $k$，最多有一枚硬币面值为 $\dfrac{1}{k}$（否则两枚这样的硬币可以被合并）；对于每个奇数 $k>1$，最多有 $(k-1)$ 枚硬币面值为 $\dfrac{1}{k}$（否则 $k$ 枚这样的硬币可以被合并）．
在此情况下，先将所有面值为 $1$ 的硬币分别编为一组．如果有 $d$ 枚这样的硬币，则可以去除这样的硬币并在问题中用 $N-d$ 来代替 $N$．因此我们不妨假设此时没有面值为 $1$ 的硬币．
我们按如下方式将硬币进行分组．对于 $1,2,\ldots,N$ 中的每个正整数，将所有面值为 $\dfrac{1}{2k-1}$ 和 $\dfrac{1}{2k-2}$ 的硬币放入第 $k$ 组，则第 $k$ 组中所有硬币的面值之和不超过
$
(2 k-2) \cdot \dfrac{1}{2 k-1}+\dfrac{1}{2 k}<1
$
然后再考虑所有面值小于 $\frac{1}{2N}$ 的硬币，将它们依次放入各组当中．每次选择一枚这样的硬币，必有某一组中硬市的面值之和不超过 $1-\dfrac{1}{2N}$（否则各组硬币的面值总和将大于 $N(1-\dfrac{1}{2N})=N-\dfrac{1}{2}$，与已知条件矛盾），那么就将这样小面值的硬币放入该组中，则该组硬币的面值之和不超过 $1$．重复这样的操作，我们就把所有的硬币按要求分成了至多 $N$ 组．证毕!
答案
解析
备注
