ビリヤード玉の問題再考（２）

森博嗣さんの『笑わない数学者』の中でのビリヤード玉の問題についてあらためて考えています。

五つのビリヤードの玉を、真珠のネックレスのように、リングでつなげてみるとしよう。玉には、それぞれナンバが書かれている。さて、この五つの玉のうち、幾つ取っても良いが、隣どうし連続したものしか取れないとしよう。一つでも、二つでも、五つ全部でも良い。しかし、離れているものは取れない。この条件で取った玉のナンバを足し合わせて、1から21までのすべての数ができるようにしたい。さあ、どのナンバの玉を、どのように並べて、ネックレスを作れば良いかな？

最終的には \( n \) 個のビリヤード玉で解が存在するかどうか、存在するとすればその求め方、存在しないとすればその証明などを明らかにしたいと思いますが、そこまで行き着けない可能性もあります。

まずは、5個のビリヤード玉での解法を確認します。解法といっても、僕が以前に解いたやり方（場合分けによる総当り的なやり方）ですので、もう少しスマートな解法があるかもしれません。あらためて解くことで、そういった解法に出会えるかもしれませんし、当たり前と思ってさらっと流していた条件などに気づけるかもしれませんので、もう一度あらためて解いてみたいと思います。なので少し細かく書いているので冗長な部分があるかと思います。

条件とか、ここでの表記の仕方についての確認しながら解いていきます。

5個のビリヤード玉を、Ａ・Ｂ・Ｃ・Ｄ・Ｅとして、この順で右回りにリングでつながっているとします。Ａ－Ｂ－Ｃ－Ｄ－Ｅ（－Ａ）とつながっていて、最後のＥとＡがつながってリング状になっている状態です。書かれているナンバは自然数とします。5つの玉のうち、幾つ取っても良いが隣どうし連続したものしか取れません。この条件で取った玉のナンバを足し合わせて、1から21までのすべての自然数ができるようにします。

問題の条件での玉の取り方が何通りあるかを数えると、\( 21 \) 通りあります。まずは、1個を取る場合。これはＡを取るか、Ｂを取るか、Ｃを取るか、Ｄを取るか、Ｅを取るかの5通り。2個の場合は、Ａ－Ｂ、Ｂ－Ｃ、Ｃ－Ｄ、Ｄ－Ｅ、Ｅ－Ａの5通り。3個の場合は、Ａ－Ｂ－Ｃ、Ｂ－Ｃ－Ｄ、Ｃ－Ｄ－Ｅ、Ｄ－Ｅ－Ａ、Ｅ－Ａ－Ｂの5通り。4個の場合は、Ａ－Ｂ－Ｃ－Ｄ、Ｂ－Ｃ－Ｄ－Ｅ、Ｃ－Ｄ－Ｅ－Ａ、Ｄ－Ｅ－Ａ－Ｂ、Ｅ－Ａ－Ｂ－Ｃの5通り。5個の場合は、Ａ－Ｂ－Ｃ－Ｄ－Ｅの1通りとなります。\( 5+5+5+5+1 = 21 \) で、\( 21 \) 通りとなります。この \( 21 \) 通りで1から21までのすべての自然数をつくるので、Ａ・Ｂ・Ｃ・Ｄ・Ｅはすべて異なる自然数で、玉の取り方1つに対し、1から21までの自然数のどれかが対応することになります。

したがって、①は必ず入っていることになります。ここでは1と書かれているビリヤード玉を①と書きます。1をつくるのには①が必要です。①の場所をＡに固定して考えます。これをＡ=①と書きます。Ａ－Ｂ－Ｃ－Ｄ－Ｅ（－Ａ）とつながっているので、①－Ｂ－Ｃ－Ｄ－Ｅ（－①）となります。

そして②も必ず入っていることになります。2をつくるためには \( 1+1 \) でもつくれますが、ビリヤード玉に書かれている自然数はすべて異なる自然数となりますので、①+①という組み合わせはありません。②も必ず存在することになりますが、場所はわかりません。

また、\( Ａ+Ｂ+Ｃ+Ｄ+Ｅ=21 \) となります。Ａ・Ｂ・Ｃ・Ｄ・Ｅを場所と言ったり、文字式の中に使ったりしてしまいますが、ご容赦ください。このあたり、一般化して考えるときにはもう少し表記の仕方を考えなければならないかもです。

Ａ=①として、その隣に②があるかどうかで場合分けをして考えます。もし①の隣に②があれば、\( ①+②=3\) となり、③の玉は不要になります。逆に①の隣に②がなければ③の玉が必要になります。もし3を自然数の和で表すとすれば、\( 1+2 \) しか存在しないためです。（Mathjaxを使って書いており、フォントが異なってしまっているところがあります。フォントの違いは無視してください。区別しなければならないときはその旨記載します。）

Ａ=①の隣ということは、ＢかＥとなりますが、ＢでもＥでも裏返して考えると同じになるので、ここではＢ=②かどうかで考えます。


(i) ①の隣に②がある場合（Ｂ=②の場合）
つまり、①－②－Ｃ－Ｄ－Ｅ（－①）の場合です。

残りのＣ・Ｄ・Ｅについて考えると、①、②は使われていて、3は①+②で不要ですので、4以上の自然数となります。また、\( Ａ+Ｂ+Ｃ+Ｄ+Ｅ=21 \) ですので、\( Ｃ+Ｄ+Ｅ=18 \) です。このような相異なる自然数の組となるものは、{ ④, ⑤, ⑨ } { ④, ⑥, ⑧ } { ⑤, ⑥, ⑦ } の3組です。{}でくくった組み合わせは順番関係なしの組み合わせとします。このうち { ⑤, ⑥, ⑦ } では4をつくることができませんので、残るは { ④, ⑤, ⑨ } { ④, ⑥, ⑧ } です。

④が存在しなければならないことになるので、④が①－②－Ｃ－Ｄ－Ｅ（－①）のどこに入るかを場合分けして考えます。

(i-a) Ｃ=④の場合
つまり、①－②－④－Ｄ－Ｅ（－①）の場合です。

この状態では5をつくることができませんので⑤が必要となり、Ｃ・Ｄ・Ｅの組み合わせは、{ ④, ⑤, ⑨ } となります。しかし、①－②－④－⑤－⑨（－①）としても、①－②－④－⑨－⑤（－①）としても、1から21までのすべての自然数をつくることができませんので、Ｃ=④ではありません。

(i-b) Ｄ=④の場合
つまり、①－②－Ｃ－④－Ｅ（－①）の場合です。

この場合も⑤が必要となり、Ｃ・Ｄ・Ｅの組み合わせは、{ ④, ⑤, ⑨ } となります。しかし、①－②－⑤－④－⑨（－①）としても、①－②－⑨－④－⑤（－①）としても、1から21までのすべての自然数をつくることができませんので、Ｄ=④でもありません。

(i-c) Ｅ=④の場合
つまり、①－②－Ｃ－Ｄ－④（－①）の場合です。

この場合は、④+①で5をつくれます。したがって、Ｃ・Ｄ・Ｅの組み合わせは { ④, ⑥, ⑧ } となります。しかし、①－②－⑥－⑧－④（－①）としても、①－②－⑧－⑥－④（－①）としても、1から21までのすべての自然数をつくることができませんので、Ｅ=④でもありません。

したがって、(i)①の隣に②がある場合は解なしです。

(ii) ①の隣に②がない場合
つまり、①－Ｂ－②－Ｄ－Ｅ（－①）か、①－Ｂ－Ｃ－②－Ｅ（－①）の場合ですが、この2つは裏返すと同じものですので、①－Ｂ－②－Ｄ－Ｅ（－①）として考えます。

①と②が離れているので、③が必要になります。そこで、③の場所で場合分けして考えます。

(ii-a) Ｂ=③の場合
つまり、①－③－②－Ｄ－Ｅ（－①）の場合です。

この場合は、①、②、③、①+③、③+②、①+③+②と、6までの自然数がつくれます。7をつくるには、Ｄ=⑤とするか、ＤかＥに⑦が存在するかのどちらかです。

(ii-a1) Ｄ=⑤の場合
この場合は、\( Ａ+Ｂ+Ｃ+Ｄ+Ｅ=21 \) から、①－③－②－⑤－⑩（－①）となります。しかし、8をつくることができません。

(ii-a2) ＤかＥに⑦が存在する場合
この場合、残るひとつは⑧になります。したがって、①－③－②－⑦－⑧（－①）か、①－③－②－⑧－⑦（－①）です。しかし、どちらも1から21までのすべての自然数をつくることができません（前者は10がつくれない。後者は⑧と⑦+①で8がダブる）。

したがって、(ii-a) Ｂ=③の場合、解なしです。

(ii-b) Ｄ=③の場合
つまり、①－Ｂ－②－③－Ｅ（－①）の場合です。

この場合、④が必要となります。したがって残る1つは⑪となり、①－④－②－③－⑪（－①）か、①－⑪－②－③－④（－①）となります。しかし、どちらも1から21までのすべての自然数をつくることができません（どちらも5がダブる）。

したがって、(ii-b) Ｄ=③の場合も、解なしです。

(ii-c) Ｅ=③の場合
つまり、①－Ｂ－②－Ｄ－③（－①）の場合です。

この場合、③+①で4がつくれます。このままでは5がつくれないので⑤が必要です。⑤が決まれば、残りは⑩となります。したがって、①－⑤－②－⑩－③（－①）か、①－⑩－②－⑤－③（－①）です。後者は6がつくれません。前者の場合は、1から21までのすべての自然数をつくることができます。

念のため、確認してみましょう。

1. ①
2. ②
3. ③
4. ③+①
5. ⑤
6. ①+⑤
7. ⑤+②
8. ①+⑤+②
9. ③+⑤+①
10. ⑩
11. ③+①+⑤+②
12. ②+⑩
13. ⑩+③
14. ⑩+③+①
15. ②+⑩+③
16. ②+⑩+③+①
17. ⑤+②+⑩
18. ①+⑤+②+⑩
19. ⑩+③+①+⑤
20. ⑤+②+⑩+③
21. ①+⑤+②+⑩+③

1から21までのすべての自然数をつくれることが確認できました。

したがって、5つのビリヤード玉の問題の答えは、①－⑤－②－⑩－③（－①）となります。

さて、これを一般化して考えるにはどうすればよいでしょうか。