質問 @ 2015.1.20
質問
会費5,000円のパーティで，丸テーブルの周りに 2n 人が座っている。5,000円札を持っている人 と，10,000円札を持っている人がちょうど n 人づついるとする。ある適当な人から始めてテーブル ま周りの並びの順に，それまで集めた5,000札でおつりをうまく出しながら会費を集金する方法があ ることを示せ。
解答
i番目の人の集金に対し， を下記とする。
when 5,000札をだした,
when 10,000札をだした。
i番目の集金後，残っている5000札の枚数は下式となる。
.
は i番目までで集められた 5,000円札の枚数。
5000円札と10000円札の人が同数なので，最後の集金後で， となる。
途中で となれば，お釣りが払えず，足りなかった5000札の枚数となる。
に対して，
ならうまく集金できたということ。
集金出来なかった場合でも仮に5000札を借りて集金を続けることにすると，
列 には最小値が存在する。（5000円札を最も多く借りて集金している箇所）
その番号をjとする。（複数あってもどこでもいい）
が最小なので，
は-1,
は+1となる。
そこで，から始めて，一周し，
で終わる集金順番を考える。
1番目の人から始めたとき j-番目で が最小この順番での集金で，
この順番がそれまで集めた5,000札でおつりをうまく出しながら会費を集金する方法である。
例
| * |
* 出したお札 | * |
* |
* 注釈 |
|---|---|---|---|---|
| 1 | 5000 | +1 | +1 | |
| 2 | 10000 | -1 | 0 | |
| 3 | 10000 | -1 | -1 | |
| 4 | 10000 | -1 | -2 | 最小値 |
| 5 | 5000 | +1 | -1 | ここから集金開始 |
| 6 | 10000 | -1 | -2 | もう一つの最小値 |
| 7 | 5000 | +1 | -1 | ここから集金開始してもいい |
| 8 | 5000 | +1 | 0 |
