質問 @ 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 |
|