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枚、価値 1/(2m+1)1/(2m+1) の硬貨は高々 2m2m 枚である。価値 11 の完全なグループを取り分け、その個数を gg とする。残りの合計額は高々 9912−g=(100−g)−1299\tfrac12-g=(100-g)-\tfrac12 である。