月草色の幻影 Official Site

皆さん今日は、Alhenaです。
何時の間にか11月ももう下旬に入ろうとしていますが、如何お過ごしでしょうか。

……9月にⅢ章いけるかも、なんて言っていたのがつい昨日のことのように思えます。光陰矢のごとしとは良く言ったものですね。
いい加減充電期間も終わらせなければ。



さて、今日の話題は3回前に投稿したビリヤードの玉の問題についてです。
皆さん解けましたか？
以下一部解法に触れますので、自力で解きたい方はご注意ください。

一先ず問題を再掲しておきます。

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

(森博嗣『笑わない数学者』より抜粋)


この問題を考察する上での肝は、21という数字が何処から出てきたかということにあるのですが、此処を乗り越えてしまえば球の個数が5個の場合に限らず、n個の場合に拡張して考えることも比較的容易にできます。

そうは言っても答えが規則的に現れる訳ではないので、同じ考え方が使えると言うだけですが、同じ考え方が使えるということは、機械的に解法をプログラムできるということになります。

そんな訳で例によってRGSSで手慰みに書いてみたのですが、それを出す前に先ず21の持つ意味を説明しますと、これは5個の玉の取り方の数になります。
取る玉の数1～4個に対して、取り始める点が5か所ずつ、それに全て取った場合の1通りを加えて 4*5+1=21 通りですね。
n個に拡張した場合は n(n-1)+1 通りになります。

また、これは全ての取り方に於いて球の数の和に重複は存在しないことを示しています。
例えば1と2の玉が隣り合っていたら、3の玉は絶対に入りません。

更にこのことを考えれば、1～21の全ての数を作るという条件を、5つの玉の数の総和が21かつ全ての取り方に於いて和に重複が無い、と言い変えることができます。
こうすることで条件の一致不一致を素早く判別することができます。

以上のことを考察した上で解法をスクリプトにしてみました。興味のある方はご覧下さい。

billiards.txt


さて、これを使って計算してみると答えの個数について面白い事実が浮かび上がって来ます。
球の個数が4個の時に二つ答えが出るのは人が考えても直ぐに分かりますが、6個にすると答えは五つに増え、更に7個にすると今度は答えは存在しないのです。
球の個数が1個の時から答えの数を並べると

1→1→1→2→1→5→0→6→4→6→0→18→……

となります。
今ブログを書いているPC環境では、12個の場合を計算するのに3,4分掛かったので、これ以上は面倒で計算してませんが、こういった規則性の無さにも数字の醍醐味を感じますね。


なお、スクリプトの設計としては、先ず全ての玉に1を入れて、そのうち一つの玉の数を1ずつ増やしていき適当な数で繰り上げ、増やすたびに条件に合うかどうか調べるようなものの方が簡単かつ簡潔に書けますが、処理速度は牛歩に等しいです。