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

森博嗣さんの『笑わない数学者』の中でのビリヤード玉の問題についてあらためて考えていて、少し煮詰まってきたので Web 上で $n$ が大きいときの解の一覧がないかとか、解を見出すためのアルゴリズムにはどのようなものがあるのかを確認していたら、興味深いtweetのまとめを見つけました。

Togetter：『笑わない数学者』のパズルと目盛の節約，ゴロム分度器と完全差集合予想について

tweet内のリンク先で非公開となってしまっているところがあるのが少し残念ですが、話題として盛りだくさんな内容です。

簡単に興味あるところをピックアップして書くと、まずは考えているビリヤード玉の問題について、次のことが書かれていました。解もいくつか書かれていましたが、解の個数については明記されてはいませんでした。検証はまだしていません。

• $n = 8$ のときの解（解の個数についての明記なし）
  $$( 1, 3, 8, 2, 16, 7, 15, 5 ）$$
• $n = 10$ のときの解（解の個数についての明記なし）
  $$( 1, 2, 9, 8, 14, 4, 43, 7, 6, 10, 5, 24 )$$
• $n = 14$ までのうち，解が存在しないのは $n = 7, 11, 13$ 。この先の素数でも解は存在しない様子。
• $n = 15, 16, 21, 22$ でも解なしの模様。
• $n = 30$ のときの解（解の個数についての明記なし）
  $$( 1, 35, 17, 21, 20, 56, 7, 19, 98, 5, 29, 3, 11, 2, 62, \\ 6, 60, 25, 15, 9, 18, 4, 8, 47, 10, 23, 28, 44, 99, 89 )$$

「隣接ではなく、球のすべての組み合わせの合計でやるなら、番号 $1, 2, 4, …, 2^{n-1}$ の $n$ 個の球で $1$ から $2^{n-1}$ までの全部の整数が作ることができる。2進法。」「輪にする（＝ $mod$ で考える）だけで大きな $n$ でも完全性が成り立つようになる」というのもおもしろいです。

また、目盛節約定規、ゴロム定規について。ゴロム定規というのを初めて知りましたが、Wikipediaにも載っていて、いま考えているビリヤード玉の問題ではリング状に並んだ状態で考えていますが、ゴロム定規はリング状ではなく直線上として並んでいるようなものですね。まだ詳しくは読んでいません。そして、モジュラーゴロム定規（ゴロム分度器）。詳しく書かれているわけではありませんが、ビリヤード玉の問題と同じような気がします。すでに定理となっているのか予想のままなのかはわかりませんが、「$n-1$ が素数か素数の羃のとき、かつそのときに限って、目盛数 $n$ の完全ゴロム分度器が存在するであろう」という有名な予想があるようです。おそらくはこの予想のことを指していると思いますが、$n \lt 1600$ ではこの予想が成り立っていることが Evans & Mann によって確かめられているみたいです。

興味をひいたのは、完全差集合という言葉です。$n-1$ が素数か素数の羃ならば、$mod \ n(n-1)+1$ で完全差集合になる $\{ a_1, a_2, …, a_n \}$ が存在することを、Singer が証明しているらしく、tweet主がビリヤードの問題と「完全差集合」と本質的に同じであることをつぶやいています。$n(n-1)+1$ はビリヤードの問題にも出てきました。

Wikipediaには「完全差集合」の項はありませんでした。「差集合」の項がありましたが、完全差集合での差集合とは違うものかと思われます。

tweetのリンク先には英語で書かれているサイトも含まれているので、ななめ読みしかしていませんが、完全差集合は英語で perfect different sets でしょう。もうひとつ、cyclic difference sets というのもリンク先にありました。日本語ではどうやら「巡回差集合」と訳されているようです。

完全差集合、巡回差集合について確認してみます。