パズルの国のアリス

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

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

 最初の問題だが,4枚の小切手の中に同額のものがあれば,まずそれを2人で1枚ずつ取ればよいから,小切手の額面が全部違っていない限り,全部を伯父に返すことはない。1から8までの目から重複がないように4種の目を選ぶのは8C4=70通りあるが,この程度なら,全部を調べて,双子がうまく同額を取れないような組み合わせを探すことが可能だ。実際,そのようにして調べた組み合わせを辞書式に羅列すると,1-2-4-8,1-4-6-8,2-3-4-8,2-4-5-8,2-4-7-8,3-4-6-8,3-5-6-7,3-6-7-8,4-5-6-8,4-6-7-8の10通りがある。

 ついでながら,正八面体ではなく,普通の立方体サイコロを4つ振って同じことを行った場合は,全部の小切手を返さざるを得なくなることはない。1から7の目が出るルーレットを使った場合は,上のリストにある3-5-6-7が出たときを例外として,双子は何がしかの小遣いを得る。

 第2の問題は,しらみつぶしに調べて解こうとすると100C10通りを検討しなければならなくなる。うまく探索すれば,いくつかのパターンはまとめて処理できるから,実際に調べるパターンはずいぶんと減らせるとはいえ,そのような調査はコンピューターでやっても簡単ではあるまい。

 しかし,実は,先の10通りの組合せに共通する性質に気がつけば,しらみつぶしの調査など行わなくとも,比較的簡単な推論だけで結論が得られるのだ。それは,4つの数からいくつか選んでその和をとることで作れる数が何種類あるかを考えることだ。

 わかりやすい1-2-4-8で検討してみよう。2進法を学んだことがあればすぐわかるように,1,2,4,8からいくつかを選んで足し合わせることで,0から15までのすべての整数,すなわち16種類の整数が作れる。これは他の組合せでも同じことで,次の1-4-6-8からも,最後の4-6-7-8からも,(実際に作れる数値は違っているが)全部で16種類の数が作れる。この性質こそが,まさに双子が得る金額をゼロにする要因なのだ。

 数の集合Aの要素の総和をAの重みと呼ぶことにしよう。一般に集合Xのサイズ(要素の数)をnとするとき,Xは全部で2n種類の部分集合を持つ。Xの各部分集合の重みを考えたとき,その値がことごとく異なっていれば,つまり全部で2n種類の重みがあれば,Xからの異なる2つの部分集合ABを選び出し,その重みを一致させることは明らかに不可能である。逆に,重みの種類が2n未満しかない場合,(部屋割り論法により)重みが一致する2つの異なる部分集合ABがある。ABは共通の数を含むかもしれないが,両方からその数を取り去った部分集合同士を考えても,重みは一致したままだからABには共通部分がないとしても一般性を失わない。

 さて,以上の考察を100以下の正の整数からなるサイズ10の集合Xに適用してみよう。Xは210=1024種類の部分集合を持つ。これらの部分集合は,どういう重みを持ちうるだろうか?要素はすべて正の数だから,明らかに重みが最小になるのは空集合の場合で,その重みは0だ。最大になるのは,X全体の場合だが,Xの要素はどれも100以下の整数だから91+92+…+100=955以下だ。もちろん重みは整数値だから,Xの部分集合が取りうる重みの可能性が956種類を超えることはない。従って1024種類の中には,同じ重みを持つ異なる部分集合ABで互いに共通部分を持たないものが存在する。Xを伯父のルーレットが出した目の集合とすると,ダムがAに属する数値を額面として持つ小切手を取り,ディーがBに属する数値を額面として持つ小切手を取れば,全部を伯父に返す羽目になることはない。

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

問題はこちらです