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−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 以下に保って入れられる。