MathLabs

第5题

对每个正整数 nn,开普敦银行发行面值为 1n\tfrac{1}{n} 的硬币。给定这样一批硬币(面值不必互不相同)的有限集合,其总价值不超过 99+1299+\tfrac12,证明可以把这批硬币分成不超过 100100 组,使得每组的总价值都不超过 11。
第 5/6 步：平均论证总能找到空位
上一步下一步
each box has slack ≥12r>12r+1\text{each box has slack }\ge\tfrac1{2r}>\tfrac1{2r+1}
详细分析

逐枚放入堆中的硬币。若下一枚无法放入任何箱子，则每个箱子的价值都大于 1−1/(2r+1)1-1/(2r+1)，箱中总价值超过 r−r/(2r+1)r-r/(2r+1)。但剩余总价值至多为 r−1/2r-1/2，且 r−r/(2r+1)>r−1/2r-r/(2r+1)>r-1/2，矛盾。因此堆中每枚硬币都能放入某个箱子，同时保持每箱价值不超过 11。