第5题

对每个正整数

n

,开普敦银行发行面值为

\tfrac{1}{n}

的硬币。给定这样一批硬币(面值不必互不相同)的有限集合,其总价值不超过

99+\tfrac12

,证明可以把这批硬币分成不超过

100

组,使得每组的总价值都不超过

1

。

第 1/6 步：两种不损失价值的合并操作

上一步下一步

\underbrace{\tfrac{1}{2m}+\tfrac{1}{2m}}_{2} = \tfrac{1}{m}, \qquad \underbrace{\tfrac{1}{2m+1}+\cdots+\tfrac{1}{2m+1}}_{2m+1} = 1

详细分析

在可能的情况下重复以下两种不改变总价值的操作:若面值 $\tfrac{1}{2m}$ 的硬币出现两枚,把这一对替换为一枚面值 $\tfrac{1}{m}$ 的硬币;若面值 $\tfrac{1}{2m+1}$ 的硬币出现 $2m+1$ 枚,把这 $2m+1$ 枚全部取出,单独作为一个完整的组(总价值恰为 $1$ )。每次操作都严格减少硬币数量,因此该过程必然终止。