0.はじめに
森博嗣さんの「笑わない数学者」を読んだのはもう随分前のことになる。未読の方は面白いので是非とも読んで欲しいと思う。ミステリーとしては異色の作品だと思う。有名な「すべてがFになる」が話題になりその後に読んだのだと思うが今となっては記憶が曖昧だ。この記事を書くきっかけとなった, @TETSURO1999 さんのQiitaの記事
によると,
1996年04月05日 小説「すべてがFになる」講談社，森博嗣
1996年09月02日 小説「笑わない数学者」講談社，森博嗣
らしいので, 30年ほど前でおそらくは「すべてがFになる」を読んだ後に手に入れて読んだのだろう。この「笑わない数学者」の中には幾つも数学絡みの問題が現れるのだけど, そのうちの作中に回答が示されていない「ビリヤード問題」は読みながら片手間に解いては見たもののずっと気になっていた。
1.ビリヤード問題
問題は,
五つのビリヤードの玉を真珠のネックレスのようにリングにつなげてみるとしよう。玉にはそれぞれナンバーが書いてある。さて，この五つの玉のうち幾つ取っても良いが，隣どうし連続したものしか取れないとしよう。一つでも二つでも五つ全部でも良い。しかし離れているものは取れない。この条件で取った球のナンバーを足し合わせて１から２１までのすべての数ができるようにしたい。さあ，どのナンバーの玉をどのように並べてネックレスを作ればよいかな？
というもので, 作中で「伝説的数学者」な「天王寺翔蔵博士」が出題する問題だ。本当に博士が出題した(という設定な)のかどうかも実は分からないのだけど。
初見だと問題の意図や内容が分かりにくいかもしれないので, 図を付けておきます。
|
「左側の円状に並んだ5つの⚪︎に, 右の1から15のビリヤードの玉から5つ選んで並べます。ただし, 隣り合う玉の数を足し合わせることで, 1から21の数ができるようにして下さい。」ということです。1〜15までというのは, 幾つかあるビリヤード・ゲームの中で, よく知られているポケット・ビリヤードと呼ばれるもので使う番号の書いてある玉が, 1〜15だからです。
玉の数を変えてみましょう。例えば, 「4個の玉を並べて」とするとどうでしょう。答えは2通りあります。そのうちの一つを次に図で示してみたので, もう一つの解は色々試して各自で探してみて下さい。この程度の大きさなら手作業で直ぐに見つかると思います。
玉は4つ並んでいますから, 玉を1つだけ取る場合は4通り, 2つの場合も4通り, 3つの場合も4通りの取り方(隣り合う玉を取る)がありますから, これに4個全て取る場合を合わせて, $4\times 3+1=13$通りの取り方があります。したがって, 「一つでも二つでも四つ全部でも良い。しかし離れているものは取れない。この条件で取った球のナンバーを足し合わせて１から１３までのすべての数ができるようにしたい。」となるわけです。ちなみに元の問題で「1から21まで」となるのも$5\times 4+1=21$だからなんだということに気がつきましたか。よくできた問題です。当時はその程度の認識でした。
2.歳月が過ぎて...
当時も確かBASICでプログラムを書いて, 答えを確かめたり, 4個の場合は2組答えがあり, 6個だと
$(1,2,5,4,6,13), (1,2,7,4,12,5), (1,3,2,7,8,10), $
$(1,3,6,2,5,14), (1,7,3,2,4,14)$
の5組の答えがあるが, 7個だと答えが見つからない。でも8個だと,
$(1,2,4,8,16,5,18,9,10), (1,4,7,6,3,28,2,8,14),$
$(1,6,4,24,13,3,2,12,8), (1,11,8,6,4,3,2,22,16)$
の4通りある... といったことは確認できていました。不思議だなぁとは思ったもののそれほど深く考えることはありませんでした。
それが何年か前に, ネットを検索しているときに, もっと大きなものも作れるというような話を見掛けて, それから思い出して時間があるときに色々探索していて,
Cyclic Difference Sets - by Kris Coolsaet
というページに行き当たりました。ここは正にこの魔円陣というか, (完全円状)差集合について, 研究者が一般人に解説をするページだったのですが, 作者は故人のようで, 行き当たったときには誰か別の人が勿体無いから再構築？したものという感じでした。
暫くこのページを訳したりしながら様々考えたりもしたのですが, 肝心な部分がよく分からずその内放置してました。
因みに, 適当に翻訳しながら纏めたものはこちらにあります。ブログの題は「久々に使うとすっかり忘れてるけど」となっていますが, 中に2つの文書が置いてあります。
最近になって, @TETSURO1999 さんがQiitaでこの問題を連載されていたのを発見し,
これは！となって, Julia で解いてみたという話です。最近漸くプログラムも纏まってきたのでここに纏めておこうと。
3. 確認し直したこと
一応理学部数学科を卒業したので, 代数学も一通りは学んだ筈なのですが, 色々足りない部分があるので確認に時間が掛かりました。時間も取れないし気力も保たないので摘み食いでの確認です。
「有限射影平面概観」というpdf
や, 数学セミナーに掲載された「魔円陣と有限幾何」
はとても勉強になりましたが, それらを単独で読んでいてもすんなりとは理解できませんでした。
色々と確認しながら, Juliaだと, NemoというPkgで有限体を具体的に扱えるということで, 所謂代数学的な確認は念頭に置かずに, 機械的に「問題を解く」ことを目標に確認を進めました。
具体的に確認したことは, 「有限体を3次拡大すれば有限射影平面を拵えることができる」という話です。そこには「そもそも有限体とは何か」とか「射影平面とは何か」という事が絡んできますが, 「juliaでNemoというPkgを用いての機械的な作業」という事だと, Nemoのコマンドの確認と, 出来上がったものを確認するだけで良いので, 「わかった気になる」には十分でした。
ただ, 単純な素数$p$を位数とする有限体$GF(p)$と素数の冪乗$p^n$を位数とする拡大された有限体$GF(p^n)$では, それらの3次の既約多項式を確認するのも, そこから得られる生成元／原始元を確認するのも, 少し要領が異なる$GF(p^n)$の場合に多少手数が加わるところがあるので, その辺りが面倒だったかも知れません。
実際のjuliaのプログラム「魔円陣をサイズが小さいものから列挙する」
を見れば分かるでしょうか。
このプログラムでは, 「魔円陣をサイズが小さいものから列挙する」という表題にもある通り, $GF(p)$用と$GF(p^n)$用の2つの関数を用意してから, 素数冪を小さい順に用意して, それらに何方かを適用して魔円陣を拵えて列挙しています。
4. できあがったビリヤード問題の解／魔円陣は...
最初の方の小さなサイズの魔円陣の結果を引いておくと,
p=2, n=1, q=2, q^2+q+1=7, q+1=3, q^3+1=9, Number of MagicCircles = 1
(1,2,4)
かかった時間(途中経過): 156 milliseconds
p=3, n=1, q=3, q^2+q+1=13, q+1=4, q^3+1=28, Number of MagicCircles = 2
(1,2,6,4), (1,3,2,7)
かかった時間(途中経過): 165 milliseconds
p=2, n=2, q=4, q^2+q+1=21, q+1=5, q^3+1=65, Number of MagicCircles = 1
(1,3,10,2,5)
かかった時間(途中経過): 165 milliseconds
p=5, n=1, q=5, q^2+q+1=31, q+1=6, q^3+1=126, Number of MagicCircles = 5
(1,2,5,4,6,13), (1,2,7,4,12,5), (1,3,2,7,8,10), (1,3,6,2,5,14), (1,7,3,2,4,14)
かかった時間(途中経過): 166 milliseconds
p=7, n=1, q=7, q^2+q+1=57, q+1=8, q^3+1=344, Number of MagicCircles = 6
(1,2,10,19,4,7,9,5), (1,3,5,11,2,12,17,6), (1,3,8,2,16,7,15,5), (1,4,2,10,18,3,11,8), (1,4,22,7,3,6,2,12), (1,6,12,4,21,3,2,8)
かかった時間(途中経過): 167 milliseconds
のようになっています。
$p$ は元になる有限体の素数位数。素数そのままの場合は $n=1$ ですが, 素数冪の場合は $n=2,3,...$ となります。 $q$ は実際に使う有限体の位数です。 $n=1$ なら $p$ そのままですから $q=p$ で同じ数が表示されています。 $n>1$ の場合は $q=p^n$ ですから, $p=2,n=2$ の場合は $q=2^2=4$ となっています。魔円陣の大きさは $q+1$ です。
同じサイズの魔円陣の数をNumber of MagicCirclesという一寸変な英語で表してますが...
で, 実際の魔円陣に並ぶ数がリスト表示で列挙されています。
$p=7$ で有限体 $GF(7)$ を元にして, 3次拡大して有限射影平面を拵えて, その巡回平面の一つから得た魔円陣を確認すると, サイズは $q+1=p+1=8$ のものが６つ現れ, $p=2,n=2$ で有限体 $GF(2^2)$ を元にして, 3次拡大して有限射影平面を拵えて... とすればサイズが $q+1=p^n+1=2^2+1=5$ のものが1つだけ現れるというわけです。
@TETSURO1999 さんや Kris Coolsaet の方式とは違い, 素直に有限体を拵えてその3次拡大からの有限射影平面を扱って確認しています。
上に挙げたGitHubに置いたJupyter notebookでは,
p=2, n=7, q=128, q^2+q+1=16513, q+1=129, q^3+1=2097153, Number of MagicCircles = 336
(1,2,4,8,16,32,25,39,50,78,100,156,117,83,235,18,59,234,166,275,195,36,118,468,221,66,45,521,29,165,52,173,72,53,183,269,188,276,190,13,351,91,132,19,71,215,76,46,238,42,425,58,281,49,5,99,205,34,40,67,43,101,106,103,263,65,44,270,159,9,367,519,33,283,97,26,149,226,94,138,95,182,121,143,38,23,119,21,382,27,152,17,20,55,155,164,22,135,84,443,158,136,113,47,69,199,102,70,191,98,10,105,82,11,331,79,68,80,134,51,35,202,41,171,206,139,258,129,130)
, (1,2,4,8,16,32,64,115,13,151,79,26,302,158,52,113,491,51,18,74,173,17,87,67,159,85,188,10,166,533,57,45,36,75,73,321,25,34,21,153,93,41,318,23,86,61,47,44,285,20,157,175,519,547,114,90,72,150,146,49,214,178,201,50,68,42,139,167,65,121,82,365,271,9,37,95,77,122,94,5,83,295,78,197,40,123,191,43,54,22,231,347,584,107,89,250,116,284,140,66,149,189,39,180,117,27,11,289,292,98,125,58,142,70,33,169,168,19,402,29,71,35,101,84,225,53,205,129,130)
, (1,2,4,8,16,32,64,75,53,150,73,33,19,158,123,146,66,38,109,100,107,246,292,132,76,99,119,17,70,113,155,59,163,329,491,84,9,49,176,39,83,69,13,160,25,238,34,140,205,21,89,221,118,23,92,211,157,501,229,20,94,194,360,74,11,168,18,98,352,78,65,101,138,26,79,241,50,476,68,35,134,111,410,42,29,88,61,41,80,321,55,181,46,184,365,10,47,97,180,37,395,172,435,67,296,44,51,40,188,388,5,72,90,216,86,251,148,22,336,36,45,108,43,419,54,231,27,129,130)
...
(1,412,212,206,106,103,53,78,39,132,93,186,105,76,100,60,31,141,69,65,87,23,54,123,120,62,63,12,207,138,130,174,46,101,7,49,197,17,64,114,45,124,126,24,11,403,71,205,260,307,41,92,3,199,14,98,201,193,34,128,228,90,239,9,252,48,22,29,218,8,551,21,121,37,10,26,337,520,85,66,192,38,50,30,86,67,55,27,184,6,398,28,107,32,57,165,237,386,68,256,456,180,109,4,286,79,5,13,471,33,96,19,25,15,43,61,375,16,111,846,2,143,42,242,74,20,52,251,423)
, (1,444,19,30,35,9,108,7,200,33,125,155,55,17,270,116,261,29,185,3,56,206,12,127,26,25,46,83,114,69,16,467,75,48,5,281,222,42,62,100,79,105,332,107,202,13,77,57,276,64,393,272,101,45,395,136,73,302,151,300,149,43,20,235,86,40,470,172,80,39,2,888,11,27,60,70,18,169,47,14,99,78,4,219,66,250,310,110,34,540,232,15,22,54,120,140,36,135,58,145,94,28,103,6,89,23,133,8,271,24,143,111,21,31,50,92,166,161,67,138,32,383,220,68,263,150,96,10,561)
, (1,527,133,410,187,41,240,9,215,27,103,288,3,32,115,33,127,69,7,328,330,205,114,120,112,65,144,75,80,38,164,165,308,72,261,154,36,482,31,62,11,96,17,22,139,53,34,21,23,227,51,106,5,63,42,46,175,279,102,212,10,126,84,13,12,67,61,289,171,132,255,159,8,37,49,246,30,28,71,20,252,168,26,24,134,122,493,2,83,342,264,365,145,121,197,16,74,98,435,57,60,56,142,40,19,82,403,77,18,241,52,48,89,54,125,81,163,413,6,64,230,66,207,4,43,123,15,14,655)
かかった時間(途中経過): 461361 milliseconds
という有限体$GF(2^7)$を3次拡大した有限射影平面からの魔円陣迄処理して出力しています。大きさは$2^7+1=128+1=129$で, 同サイズの魔円陣が336通りある？ことが分かります。336通りを全部出力すると大変なので, ソートを掛けたものの最初の３つと最後の３つだけを出力しています。
MacBook Pro 14inch 11.2023 Apple M3 16GB Sonoma 14.5なマシンで, 461361 milliseconds掛かっています。約461秒ですから8分弱ですね。
$GF(2^9)$で試してみたら, 大体4時間半位掛かっています。矢張り大きなものを拵えるときは, 有限体から拵えるのではなく, 線形再帰剰余数列を用いる方が処理が早いのだろうなぁと。
まだこの既約多項式の係数が関係するらしい再帰数列については実装していないので, それはまた今後の話になる。
5. 数学的(有限体や有限射影平面)な裏付け...
これは, 色々遊んでみた後に, 既に挙げた幾つかの文書を読むと何となく分かるのですが, 一番勉強になったのは, 「ボロバシュ「数学の技法〜メンフィスでコーヒーを飲みながら」という丸善出版の川辺治之さん翻訳の御本」（でも本は買ってないので...）の原著でした。
簡単に分かる範囲で読み解いてみた文書を載せておきます。
とはいえ最後の方は尻切れ蜻蛉になっているので, 適当に補っておいて下さい。川辺さんの翻訳を御本を買って確認して頂くのが一番良いかと思います。
（以下続く... 2024.8.16.）
100. 書き忘れていること
100.1 ビリヤード問題として, 当初気がついていたことの一つに, 使用するビリヤードの玉の数の最大値がある。元々の「5個の玉で1〜21まで」という場合には, 玉の数は11個までで良い。つまり, 本来？1〜15まであるビリヤードの玉だけど, 実際には1〜11迄で良い筈ではということ。
5個の玉の内12を使うと, 残りの4つの玉の合計が$21-12=9$となり, そうなると, $10$を作ることは無理となるから。そしてこの理屈は玉の数を増やしても同様に成り立つ。
玉の数が$p^n+1=q+1$個の場合, $q+1$個の玉の数の合計は$q^2+q+1$になる。このとき, 使う(用意する)ビリヤードの玉の数は, $1〜\left\lceil\frac{q^2+q+1}{2}\right\rceil$となるという事だ。$\lceil x\rceil$は所謂天井関数で「$x$未満でない最小の整数」を表します(負の数の事があるので持って回した感じに...)。
100.2 J.Singerという人の論文A THEOREM IN FINITE PROTECTIVE GEOMETRY AND SOME APPLICATIONS TO NUMBER THEORY(1938) に巡回平面などの存在についての基本的な事が書かれている。
ただし, まだ完全に読みきれてない... とほほである。
100.3 岡本吉央さんという方の講義用のスライド「離散数理工学(6)」な「離散数理工学」第6回の「離散代数:有限幾何」も参考になった。これは有限射影平面について「有限体を用いて構成できるようになる」という正にそのものの中身で具体的だったからか。