パズルの国のアリス

賞金の分割(問題)

坂井 公(筑波大学) 題字・イラスト:斉藤重之

 不思議の国と鏡の国との合同演芸会がまた近づいてきた。人気の高い催しで,特技を披露して喝采を浴びようと考える者も多く,みな出し物の練習に励んでいる。ところが,主催するトランプ王室とチェス王室は,入賞者に配る賞金をどう工面するかで頭を悩ましている。というのも近年は不況気味で,税収がかなり落ち込んでいるのだ。かといって,賞金の工面を理由に増税をするわけにもいかないから,恥を忍んで,例のマハラジャ出身ではないかと噂されるお大尽に援助を頼んでみようということになり,それぞれの王室を代表してハートのジャックと白の騎士を派遣した。

 金品をばらまく機会をいつもうかがっているお大尽は,ご満悦で「ほほー。いや,あの演芸会は実に楽しい。わしもいつも楽しみにしておる。もちろん喜んで寄付しますぞ」と言って,従者に財布を持ってこさせた。従者が財布を開けると,銀貨がぞろぞろと出てくる。「おや,あまり持ち合わせがないようじゃ」と言いながらも,銀貨は全部で315枚あった。

 「賞金の総額はこれくらいでよいかのう?」との問いに2人の使者がうなずくのを見て,「しかしご存じの通り,わしはなるべく均等に振る舞うのが好きでのう」と続ける。2 人が顔を見合わせていると,「いやいや,みんな同じ額にしようというのではない。演芸会ではせっかく順位をつけているのだから,その順に賞金額が減るのでないと,芸を披露するほうもやりがいがないしのう。だが,例えば1位が50枚なら,2位は49枚,3位は48枚というふうに順に銀貨を1枚ずつ減らしていくようにできないものかのう?」

 実は,銀貨315枚という総額は,お大尽の要請を満たす入賞者の人数の選択肢が多いという意味でラッキーだった。入賞者を1位だけにして全賞金を与えるのでも,入賞者を2位までにして賞金を158枚と157枚に分け合うのでも,要請は満たされているが,お大尽はもっと大勢に入賞させたいに違いない。さて,読者には,まずウォーミングアップとして,お大尽の要請を満たしたうえでなるべく多くの人を入賞させた場合の最大の入賞者数と1位の賞金を求めていただきたい。また,総額が315枚の場合,お大尽の要請を満たす賞金分割法はそもそも何通りあるだろうか?

 315枚という総額はラッキーだったと述べたが,お大尽と主催者にとってとてもアンラッキーな枚数というのがある。つまり入賞者を1位だけにして全賞金を1位に与える以外にお大尽の要請を満たす賞金分割法がない場合だ。次の問題としては,とてもアンラッキーな場合がどのような総額のときかを考えていただきたい。

 「入賞順位の順に銀貨の枚数が1枚ずつ減っていく」というのはとても制限の強い要請だ。これを「入賞順位にしたがって賞金枚数が減っていく」にすれば,入賞者数も賞金額もかなり自由に設定できる。n枚の銀貨を後者のように分ける方法の数をpn)と書くとしよう。例えば,総額がわずか6枚の場合でも,これを分けるには6,5+1,4+2,3+2+1という4通りがある。つまりp(6)=4だ。

 一般にpn)をnから計算するのは,簡単とは言いにくいが,実はn枚の銀貨を重複を許して奇数枚ずつに分割する方法の数と同数であることが知られている。例えば6を重複を許して奇数に分けるには5+1,3+3,3+1+1+1,1+1+1+1+1+1で,確かにp(6)=4通りある。読者はこの事実を証明できるだろうか?

 

解答はこちらです