パズルの国のアリス

賞金の分割(解答)

 最初の問題は,まず結論を述べるなら,315を25+24+……+6+5に分けることで入賞者21人の場合に対処でき,それが可能な最大の入賞者数だ。これが最大であることは,入賞者数をさらに増やそうとすると,1位の賞金は24枚以下だから賞金総額は最大でも24+23+……+2+1=(24×25)/2=300となり,315に満たなくなることからわかる。そもそも何通りの賞金分割法があるかという問題,試行錯誤以外で入賞者数が最大になる分割法をどうやって見つけるかという問題については,後続の問題も絡めながら,検討していくことにしよう。

 次の問題は,お大尽の要請を満たそうとすると,1位に全額を渡す以外には方法がないような銀貨の枚数を特定することだ。そのために比較的少ない枚数を調べていくことで予想を立てよう。すぐわかるのは1枚と2枚の場合で,これらは分けようがない。3は2+1に分けることができる。次に分けられないのは4枚の場合で,その次は8枚になる。以降,地道に調べていくと16枚,32枚の場合に分けられないことが判明し,ここまでくれば,2のベキ,すなわち非負の整数nにより2nと書ける枚数の場合だと予想がつく。

 さて,これはどうしてだろうか? すぐわかることをいくつか述べていくと,1位の賞金がn枚のとき,2位の賞金はn−1枚であり,1位と2位の賞金の合計は2n−1枚になる。逆に言うと,総枚数が奇数ならば必ずこのように分けられる。また,3位までを入賞とすると,3人の賞金枚数はそれぞれnn−1,n−2枚だから,合計3(n−1)枚になる。逆に言うと,総枚数が3の倍数であれば,3人に分けられる。

 このまま,4位までが入賞の場合,5位までが入賞の場合と順に増やしていってもよいのだが,奇数位までが入賞の場合をまず一般化しよう。mが正の整数のとき2m+1位までを入賞とすると,賞金総額が2m+1の倍数,すなわち(2m+1)ppは整数)の形でかつpmならば,賞金額を順にpmpm−1,……,pm+1,pmとすることでお大尽の要請が達成される。pmの場合,このままでは最下位の賞金額pmが0以下になってうまくいかないのだが,実は,下位2(mp)+1人の賞金mpmp−1,……,pm+1,pmの合計が0になっていることに気づくと,上位2p人の賞金額pmpm−1,……,mp+2,mp+1の合計が(2m+1)pであり,2p位までの賞金分割を与えることがわかる。逆に偶数2p位までの分割は,1位の賞金をpmとすると,0や負の賞金額を用いた2m+1位までの分割に変換することができ,どちらも賞金総額は(2m+1)p枚となる。

 以上より,お大尽の要請を満たす賞金分割が存在する場合,入賞者数が奇数であろうと偶数であろうと賞金総額は(2m+1)pという形でなければならず,1位の賞金はpmだとわかる。当然,賞金総額は奇数の約数を持たねばならないし,ちょうど奇数の約数の数だけの分割方法が存在する。

 総額が2n枚の場合,2nは1以外の奇数の約数を持たないので,全額を1位に渡す以外に分割法はない。総額が315枚の場合,315=32×5×7だから,315の奇数の約数は(2+1)×(1+1)×(1+1)=12個ある。よってその分割法も12通りだ。具体的には,315=(2m+1)pには2m+1とpの組として下の表のような可能性があり,それぞれが1位賞金をpm枚とする分割

 315=106+105+104
   =39+…+31=65+…+61
   =28+…+14=29+…+16
   =48+…+42=25+…+5
   =36+…+27=26+…+9
   =55+…+50=158+157

を与える。これらの中で入賞者数が最大なのは1位の賞金pmが最小となる分割法だ。

 最後の問題は,お大尽の要請をはずし,「賞金額が順位に従って減っていく」という条件だけにした場合のn枚の銀貨の分割方法の数pn)が,賞金額の重複はあってもよいが奇数枚にのみ分割する場合の分割方法の数と等しくなることの証明だ。参考にした書籍「Integer Partitions」(G. E. アンドリュース/K. エリクソン著,Cambridge University Press)によれば,この事実はオイラー(Leonhard Euler)が発見したそうだが,具体的なpn)の式を与えなくても証明できることが面白い。

 オイラーによる証明は,母関数を利用したようだが,ここではもっと平易な組み合わせ論的考察によるものを紹介しよう。それは,賞金額が次第に減っていく分割と奇数枚だけへの分割との間で1対1の対応を作るという方法だ。勝手な分割を考えると,同じ数の重複があるかもしれないし偶数を含むかもしれないが,それが偶数2kを含むときにその数をkkに2等分する操作(A)と,逆に同じ数kを重複して含むときに合わせて2kにする操作(B)を考えよう。(A)と(B)は明らかに逆操作であり,それらにより移り合う分割を同じグループとしてまとめよう。

 具体的にn=6の場合を考えてみると,{6,3+3}が1つのグループになり,{5+1}は単独で1グループになる。また,{4+2,4+1+1,2+2+2,2+1+1+1+1,1+1+1+1+1+1}と{3+2+1,3+1+1+1}もそれぞれグループを作る。すると,それぞれのグループに同じ数が重複しない分割と奇数だけからなる分割とが1つずつあり,それらが1対1に対応するのだ。

 詳細な証明は省くが,一般のnの場合にも,この関係は成立し,グループ数,同じ数が重複しない分割の数,奇数だけによる分割の数はいずれも一致し,pn)である。同じ数が重複しない分割は操作(A)を繰り返すことで奇数だけによる分割になり,逆に奇数だけの分割は操作(B)を繰り返すことで同じ数が重複しない分割になるから,直感的には対応は明らかだろう。

 前述の「Integer Partitions」には邦訳(『整数の分割』,佐藤文広訳,数学書房)がある。興味があれば参照されたい。

問題はこちらです