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 の硬貨は高々1枚を B0B_0 に入れる。各 m=1,…,r−1m=1,\dots,r-1 について、価値 1/(2m+1)1/(2m+1) の高々 2m2m 枚と価値 1/(2m+2)1/(2m+2) の高々1枚を BmB_m に入れる。その価値は高々 2m/(2m+1)+1/(2m+2)<12m/(2m+1)+1/(2m+2)<1 である。ここで r=100−gr=100-g だから、箱と完全なグループの合計は 100100 個になる。 gg