読者です 読者をやめる 読者になる 読者になる

岩大 補修教育

質問 @ 2015.1.20

質問

会費5,000円のパーティで,丸テーブルの周りに 2n 人が座っている。5,000円札を持っている人 と,10,000円札を持っている人がちょうど n 人づついるとする。ある適当な人から始めてテーブル ま周りの並びの順に,それまで集めた5,000札でおつりをうまく出しながら会費を集金する方法があ ることを示せ。

解答

i番目の人の集金に対し,{x_i} を下記とする。

{x_i = +1} when 5,000札をだした,

{x_i = -1} when 10,000札をだした。

i番目の集金後,残っている5000札の枚数は下式となる。 {\displaystyle
S_i = Σ_{k=1..i} x_k
}.

{S_i} は i番目までで集められた 5,000円札の枚数。

5000円札と10000円札の人が同数なので,最後の集金後で,{S_{2n}=0} となる。

途中で {S_i \le 0 }となれば,お釣りが払えず,足りなかった5000札の枚数となる。

{i=1..2n} に対して,{S_i \ge 0} ならうまく集金できたということ。

集金出来なかった場合でも仮に5000札を借りて集金を続けることにすると,

{{S_1..S_{2n}}}には最小値が存在する。(5000円札を最も多く借りて集金している箇所)

その番号をjとする。(複数あってもどこでもいい)

{S_j}が最小なので,{x_j}は-1, {x_{j+1}}は+1となる。

そこで,{x_{j+1}}から始めて,一周し,{x_j}で終わる集金順番を考える。

1番目の人から始めたとき j-番目で{S_j} が最小この順番での集金で,

この順番がそれまで集めた5,000札でおつりをうまく出しながら会費を集金する方法である。

* {i} * 出したお札 * {x_i} * {S_i} * 注釈
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