Note191 キス出来る人数(Kissing number)

ちょっと息抜きに。

単位円の周囲とキス出来る単位円は幾つあるか？。もちろん６個でそれ以上はキスできない。

では３次元、つまり単位球ではどうだろうか？

１個は当然キスできる。２個、３個、４個とキス出来ている。この問題についてはI.Newton とJ.Gregory が調べている（１６９４年）。最大１２個（以上）だというのは分かる。

実際にやってみると結構隙間があるのでこの隙間を寄せ集めてもう１個並べられそうだが、結局Newton にも分かりませんでした。そしてこの問題が解かれたのはおよそ２００年以上経った１９５３年、B.L. van der Waerden とK. Schutte によって１３個は無理で最大１２個である事が証明された。

ちなみにCGは最適化計算の手法で球の位置を求めた。

もっと賢いやり方はあるんだろうけど考えるのが面倒だったので上の式をそのまま計算させた。球が重ならないようにペナルティー法で制約条件を付加した。

４次元の場合はどうなのか？
２４個だそうだ。２４個である事が証明されたのはつい最近２００３年(O. Musin)。