パズルの国のアリス

不思議の国のビリヤード(解答)

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

 最初の問題は,最初に落とされた 3番を境に,ハリネズミを番号の小さい1〜2番の下位グループと,4〜15番の上位グループに分けると考えを整理しやすい。少し考えればわかるように,この下位グループと上位グループそれぞれの中ではポケットに落とされる順番が定まっている。たとえば,2番より先に 1番が落とされることはありえない。というのは,2番が落ちていない限り,既に落ちている番号と1番が1違いになることなどありえないからだ。同様に4〜15番の中ではポケットに落ちる順は4が最初で15が最後になる。したがって,2番目に落ちるハリネズミから15番目に落ちるハリネズミまでそれらが上位・下位のどちらに属するかだけで番号順は定まる。同じグループのハリネズミを区別せずに,下位グループ2匹と上位グループ12匹,計14匹を並べる順は明らかに

201411-a-img1

通りある。

 次の問題は明らかに,最初に落ちたハリネズミが何番であるかというバリエーションが加わる。たとえば最初に落ちたのが1番であれば,あとは2番から順に15番まで落ちるしかないし,反対に15番が最初ならあとは14番から順に下がっていくしかないが,最初に落ちたのが2〜14番だと落ちていく順はもっと多様になる。しかし,最初に落ちた番号をiとすれば,上で見たようにグループを2つに分けて考えることにより,ポケットしていく順には14Ci−1通りの可能性があることが簡単にわかる。iには1から15までの可能性があるから,それぞれを足して

201411-a-img2

通りが第2の問題の答えだ。高校の数学IIで習う二項定理によればこの値が 214=16384になることを知っている読者も多かろうと思う。

 実は,上の考え方を経ずにこの答えに辿り着くことができる。それは最初に落ちた番号で分類するのではなく,逆に最後に落ちた番号から考えることだ。ポケットされる番号がその時点ですでにポケットされている番号のどれかと1違いでなければならないということは,最初は1つの番号から始めるのだから,いつの時点でもポケット済みの番号が1つながりになっていることを意味する。とすると最後に落ちたのは1か15だとわかる。そうでないと,最後から1つ前の段階では,ポケット済みの番号が1つながりではなくなるからだ。それをビリヤード台に戻して考えると,14番目に落ちたハリネズミは,同様にそのとき台の上にない番号のうち,最小か最大のものだとわかる。以下,ハリネズミを台に戻しながら逆に進めていくと,各時点で台に戻すべきハリネズミの番号はいつも,台の上にない番号のうちの最大か最小のどちらかだから2通りである。例外は最後に戻すべきハリネズミ(すなわち最初にポケットしたハリネズミ)で,これはただ1匹だから1つに定まる。こうして,逆順に辿ると2肢選択が14回起こることになり,全部で214通りの場合があることになる。ついでながら,一般のn匹の場合に,最初の式の立て方とこの論法とを対照することで,二項定理の証明も得られる。

 最後の問題も,第1ショットで落ちたハリネズミの番号によって分類して,解けないこともないだろう。最初に落ちたのが1番であれば,あとは2番から順に10番まで落ちるしかないし,15番が最初なら,あとは14番から順に下がっていくしかないのは同じだ。しかし,2〜14番が最初だと,落ちた残り9匹に上位・下位グループがそれぞれ何匹入っているかでさらに分類する必要がありそうだ。

 この面倒を避けるには,逆順に考えるのが,非常に有効である。10匹がポケットされた最終段階で,その10匹がどういう顔ぶれになっているか考えてみよう。それは,連続した番号を持つ10匹だから,1番から10番までかもしれないし,6番から15番までかもしれないが,この可能性は6通りである。あとは,さっきの論法と同じである。この10匹のうち,最後に落ちた可能性があるのは最小か最大の番号を持つハリネズミで2通りある。以下,逆方向に論理を進めていくと,最初に落ちたハリネズミを除き,9番目から2番目までどこでも2通りの可能性がある。したがって,最初から連続ショットで10匹を落とす順番には, 6×29=3072通りの可能性があることがわかる。一般にハリネズミの数がn匹の場合,k匹を連続でポケットする順は,(n+1−k)2k−1通りある。

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

問題はこちらです