パズルの国のアリス

続・何が何でも取り分は同じ(解答)

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

 この問題を見て誰もが予想することは同じだろう。8個ものサイコロを振れば,その目の総和は8から64というかなり広い範囲にわたる。しかし,それを等しくするという問題ではなく,部分和同士で等しいものが作れるかという問題だから,この範囲の広さは,あまり問題にならないで済みそうだ。むしろ,サイコロを8個ずつも振るのだから,その中から適当に拾い上げれば,総額を合わせられないことなどないだろう。しかし,そのことを証明するにはどうすればよいか?

 2人が出したサイコロの目から作られる部分和には,相当のバラエティがあるので,それを数え上げる手法はどうだろうか。ダムとディーそれぞれのサイコロについて数え上げれば,その中に重なりがあるに違いない。確かにその通りなのだが,同じ目ばかりが出てしまうと部分和のバラエティは小さくなってしまう。例えば,6ばかりだと作れる部分和は6,12,…,48と8通りしかなく,7ばかりだと7,14,…,56とやはり8通りだ。この中に42という共通の部分和があるのは,偶然のようにも見えてくる。もちろん,一方がiの目ばかり,他方がjの目ばかりだとわかっているなら,ijという共通の部分和を作れることが確かだが,同じ目ばかりでない場合にこの議論をどう進めていけばよいか,今ひとつハッキリしない。

 もっと一般化して,1からnまでの目が書いてあるサイコロをn個ずつ2回振った場合,1回目で出た目から何個かを選び, 2回目で出た目から何個かを選んで,その部分和同士を一致させることができるだろうか。nが小さいときを調べてみると,確かにできる。nが大きくなってもそうだろうか?

 この種の問題にしばしば有効なのが数学的帰納法である。しかし,何の数値に関して帰納法を使えばよいだろうか? サイコロの個数だろうか? 最大が1の目のサイコロを1個振った場合は,確かに共通の部分和1が得られる。では,最大がnの目のサイコロをn個振った場合はどうか。2回振ったサイコロのどちらにもnの目が高々1つしか出ていなければ,振ったサイコロの目のうち最大のものを除くことでn−1の場合に帰着できるが,どちらかにnの目が2つ以上出ていると困る。目の総和に関する帰納法だろうか? しかし,これもうまくいきそうにない。例えば7―7―7―7―7―7―7―7と8―8―8―8―8―8―8―8の場合,共通の部分和は56しかない。それより総和が1大きい7―7―7―7―7―7―7―8と8―8―8―8―8―8―8―8の場合は,共通の部分和は8だけとなるが,この部分和8を56から導き出すような構成法がありそうには思えない。

 なかなか厄介な問題のようだが,実は,サイコロの目をどういう順番でもよいから並べてしまうことで,考え方が整理されるのだ。ダムとディーがn個のサイコロを振って,それぞれ,目a1a2,…,anb1b2,…,bnとが出たとしよう。ここで,0からnまでの整数kに対して,AkBkを先頭k個のサイコロの目の和としよう。すなわち,201311-a-imgだ。A0B0=0であり,また,AnBnは,それぞれダムとディーの出した目の総和である。問題の対称性からAnBnと仮定することができる。すると,B0B1,…,Bnは明らかに単調増加だから,各kについてBk’Akを満たすような最大のBk’が選べる。定義より,どのkについてもAkBk’は0以上でn未満の整数である(もしn以上なら,サイコロの目はnが最大だから,Bk’+1Bk’bk’+1Bk’nAkとなり,Bk’の定義に反する)。従って,部屋割り論法により,n+1個の数A0B0′A1B1′,…,AnBn’の中には,同じものが存在する。それをAiBi’AjBj’ij)とすると,AjAiBj’Bi’となるが,AjAiai+1ai+2+…+ajという部分和であり,Bj’Bi’も同様なので,2つの部分和で等しいものが存在する。

 これで双子の受取額がゼロになることがないことは証明されたが,受取額をなるべく大きくするためのうまい方法を筆者は知らない。可能な部分和をすべて調べるよりももっと効率的な方法があるなら,是非,教えていただきたい。

参考にした本
Mathematical Puzzles:A Connoisseur's Collection(2004),
Mathematical Mind-Benders(2007) P. Winkler。
邦訳は『とっておきの数学パズル』(2011年),『続・とっておきの数学パズル』(2012年),ピーター・ウィンクラー著,坂井公・ 岩沢宏和・小副川健訳,日本評論社。

問題はこちらです