パズルの国のアリス

賞金は仲良く平等に(解答)

 簡単な場合を少し試してみよう。例えば,ダムとディーのペアがもらった賞金額が8枚だとしよう。この場合,均等に分けることができるのだが,ちゃっかり者の2人は,アリスの提案を聞いてまず1枚と7枚に分割した。ともに奇数枚なので,お大尽から1枚ずつ補充してもらい,それぞれが半分を相手に渡すと5枚ずつになった。これで平等になったのでもういいだろうと思いきや,5は奇数なので,再びお大尽から1枚ずつ補充されてともに6枚になった。この調子でいつまでもお大尽の懐を当てにされると困ったことになるが,さらにやり取りを続けても2人の枚数はともに偶数の6で変化せず,分配が完了する。

 他の場合も試してみると,2人組の場合,もらった賞金額がいくらであっても,またそれを最初にどのように分配しようと,2回やり取りを行った後は状態が安定するようだ。
さて,一般にn人で同じようなやり取りを行う場合はどうだろうか。実は,少し考えれば,最初に賞金がどのように分配されていても,このやり取りで各人のところに集まる額には限界があることがわかる。最初の分配のときの最大枚数に着目しよう。その枚数が奇数の場合には,やり取りを始める前にお大尽から1枚補充されるので,最初の分配時の最大枚数は偶数2mであるとしてかまわない。以降のやり取りで各人のところに集まる額はこの2mが限界で,やり取りをいくら続けようと誰かに2m枚を超える銀貨が集まることはありえない。それは1回のやり取りごとの各人の銀貨枚数の変遷を考えれば簡単に了解できよう。

最大の2m枚の銀貨を持つ人はm枚を右隣りの人に渡して左隣りの人から何枚かをもらうけれども,それがm枚を超えることはないから,やり取り後の枚数は2m以下である。やり取り前に最大枚数未満の銀貨しか持っていなかった人は,もちろんやり取り後も2m枚未満だ。それらが奇数の場合,次のやり取りの前にお大尽から1枚補充されるが,それでも2m枚以下であることに変わりはない。

 よって,各人が持っている銀貨の枚数をすべて足し合わせても,それが2m×nを超えることはなく,お大尽が無尽蔵に銀貨を供給するという事態は生じない。

 残る問題は,状態が安定化することがなく,いつまでもやり取りが続くことがあるかだ。実は,そういうことはないのだが,その証明はやや技巧的だ。いつまでもやり取りが続くことがあったとして,矛盾を導こう。

 お大尽からの銀貨の供給がいつまでも続くことはないから,ある時点からは互いに銀貨を受け渡すだけになる。それより後を考えよう。そのようなある時点で,各人が持っている銀貨の枚数を右へ順にa1a2,……,anとしよう(輪になっているので,an枚の人の右隣りにa1枚の人がいる)。ここから先は,分配の「平等さ」加減を表す指標として,2乗和S0a12a22+……+an2を導入するのが便利だ。aiはすべて偶数で,やり取りが1回行われると各人の持っている銀貨の枚数は(ana1)/2,(a1a2)/2,……,(an−1an)/2になるから,その2乗和は

に変化する。S0S1は簡単な計算で

となる。等号が成立するのはa1a2a3=……=anのときである。これは,やり取りがさらに進んでも同じだから,2乗和の変遷を次々にS2S3,……とすると,S0S1S2S3≧……となる。各Siは正の整数だから,無限に小さくなり続けることはできず,あるiが存在してSiSi+1=0である。このときの各人の銀貨の枚数をb1b2,……,bnとするとb1b2b3=……=bnでなければならず,銀貨は完全に平等に分配され,以降のやり取りは安定していることがわかる。

問題はこちらです