MathLabs

第5题

对每个正整数 nn,开普敦银行发行面值为 1n\tfrac{1}{n} 的硬币。给定这样一批硬币(面值不必互不相同)的有限集合,其总价值不超过 99+1299+\tfrac12,证明可以把这批硬币分成不超过 100100 组,使得每组的总价值都不超过 11。
第 2/6 步:每个面值剩余数量都有上界
after termination: ≤1 coin of value 12m,≤2m coins of value 12m+1\text{after termination: } \le 1 \text{ coin of value } \tfrac{1}{2m},\quad \le 2m \text{ coins of value } \tfrac{1}{2m+1}
详细分析

无法继续合并时,对每个 mm,价值为 1/(2m)1/(2m) 的硬币至多一枚,价值为 1/(2m+1)1/(2m+1) 的硬币至多 2m2m 枚。把价值为 11 的完整组分开,设其数量为 gg。剩余总价值至多为 9912−g=(100−g)−1299\tfrac12-g=(100-g)-\tfrac12。