MathLabs

第5問

各正の整数 nn に対して、ケープタウン銀行は額面 1n\tfrac{1}{n} の硬貨を発行する。そのような硬貨(額面は必ずしも異なる必要はない)からなる有限個の集まりで、合計額が 99+1299+\tfrac12 以下であるものが与えられたとき、この集まりを 100100 個以下のグループに分け、各グループの合計額が 11 以下となるようにできることを証明せよ。
ステップ 1/6: 価値を失わない2種類の併合操作
12m+12m⏟2=1m,12m+1+⋯+12m+1⏟2m+1=1\underbrace{\tfrac{1}{2m}+\tfrac{1}{2m}}_{2} = \tfrac{1}{m}, \qquad \underbrace{\tfrac{1}{2m+1}+\cdots+\tfrac{1}{2m+1}}_{2m+1} = 1
詳しい解説

可能な限り次の2つの操作を繰り返す。これらは合計額を変えない:額面 12m\tfrac{1}{2m} の硬貨が2枚あれば、そのペアを額面 1m\tfrac{1}{m} の硬貨1枚に置き換える;額面 12m+1\tfrac{1}{2m+1} の硬貨が 2m+12m+1 枚あれば、それら 2m+12m+1 枚すべてを取り除き、それ自体を1つの完全なグループ(合計額はちょうど 11)としてよける。各操作で硬貨の枚数が厳密に減るので、この処理は終了する。