MathLabs

第5题

对每个正整数 nn,开普敦银行发行面值为 1n\tfrac{1}{n} 的硬币。给定这样一批硬币(面值不必互不相同)的有限集合,其总价值不超过 99+1299+\tfrac12,证明可以把这批硬币分成不超过 100100 组,使得每组的总价值都不超过 11。
第 3/6 步：把余下的大额硬币装入箱子 B0,…,B99B_0,\ldots,B_{99}
上一步下一步
r:=100−g,B0,…,Br−1r:=100-g,\quad B_0,\dots,B_{r-1}
详细分析

把至多一枚价值 1/21/2 的硬币放入 B0B_0。对每个 m=1,…,r−1m=1,\dots,r-1，把至多 2m2m 枚价值 1/(2m+1)1/(2m+1) 的硬币和至多一枚价值 1/(2m+2)1/(2m+2) 的硬币放入 BmB_m。箱子价值至多为 2m/(2m+1)+1/(2m+2)<12m/(2m+1)+1/(2m+2)<1。由于 r=100−gr=100-g，这些箱子与完整组总共为 100100 组。 gg