Геометрия · Комбинаторика упаковок
Сколько одинаковых кругов можно вплотную приложить к одному центральному, чтобы ни одна пара не налезала друг на друга? На плоскости ответ элементарен и доказывается за пять строк. В пространстве тот же на вид вопрос — предмет спора между Ньютоном и Грегори, растянувшегося на 259 лет.
В 1694 году Исаак Ньютон и шотландский астроном Дэвид Грегори спорили: сколько одинаковых шаров можно расположить так, чтобы каждый касался одного центрального шара того же радиуса, а сами шары не налезали друг на друга? Ньютон настаивал, что больше двенадцати не поместится. Грегори считал, что для тринадцатого, возможно, ещё останется место. Ни тот, ни другой не смогли этого доказать — и не потому, что были невнимательны: вопрос оказался по-настоящему трудным.
В русской математической литературе эту величину называют контактным числом. В англоязычной — kissing number («число поцелуев»): касание шаров по-английски иногда называют «поцелуем», отсюда и этот вариант названия, тоже прочно закрепившийся в литературе.
Контактным числом $K(n)$ в размерности $n$ называется наибольшее число шаров радиуса $1$ в $\R^n$, которые можно расположить так, чтобы каждый касался фиксированного центрального шара радиуса $1$, а сами шары попарно не имели общих внутренних точек.
Два шара радиуса $1$ касаются, когда расстояние между их центрами равно $2$; они налегают (пересекаются по внутренности), когда это расстояние меньше $2$.
На прямой ($n=1$) всё тривиально: у центрального отрезка-«шара» есть ровно два направления, слева и справа, — $K(1)=2$. Дальше становится интереснее.
Возьмём плоский случай: круги одного радиуса можно свободно тащить по плоскости — но не сквозь друг друга и не сквозь центральный. Как только круг вплотную подходит к соседу, он в него упирается и толкает его в сторону, а сам дальше не проходит — совсем как настоящие твёрдые предметы. Пока круг касается центрального, внутри него горит зелёная стрелка, указывающая точно в точку касания; уберите круг подальше — стрелка погаснет. При сближении круг слегка «прилипает» к соседу, если это не наложит его на кого-то ещё — так удобнее ставить их вплотную. Ниже уже расставлены три круга; добавьте ещё и на ощупь найдите, сколько их поместится вокруг центрального одновременно, не налезая друг на друга.
Виджет выше подсказывает механизм: чтобы круг касался центрального круга радиуса $r$, его центр обязан лежать ровно на расстоянии $2r$ от центра — на одной окружности («кольцо касания», та самая пунктирная линия на рисунке). Для всех кругов, которые касаются центра одновременно, единственный оставшийся параметр — угол $\theta$ на этом кольце, и вся задача сводится к тому, насколько близко друг к другу по углу могут стоять два таких круга, не налезая друг на друга.
Пусть два круга стоят на кольце касания (радиус $2r$ от центра $O$) под углом $\theta$ друг к другу. Треугольник с вершинами в центре $O$ и в центрах этих двух кругов — равнобедренный, с боковыми сторонами $2r$ и углом $\theta$ между ними. Расстояние между центрами кругов (основание треугольника) равно $2\cdot(2r)\sin(\theta/2)$.
Круги не налегают друг на друга ровно тогда, когда это расстояние не меньше $2r$ (суммы их радиусов):
Итак: два круга на кольце касания не налегают друг на друга тогда и только тогда, когда угол между ними не меньше $60^\circ$. Это в точности условие, которое проверяет виджет выше при каждом перетаскивании.
Допустим, на кольце стоит $m$ кругов. Идя вдоль кольца, они делят полный угол $360^\circ$ на $m$ промежутков между соседями, и промежутки в сумме дают ровно $360^\circ$. Если $m\ge7$, средний промежуток равен $360^\circ/m\le360^\circ/7\approx51{,}4^\circ$ — меньше $60^\circ$. А раз средний промежуток меньше $60^\circ$, найдётся и хотя бы один промежуток меньше $60^\circ$ (иначе сумма всех промежутков была бы не меньше $7\cdot60^\circ=420^\circ>360^\circ$ — противоречие). Значит, у этой пары соседей нарушено угловое условие — они налегают друг на друга. Вывод: $m\le6$.
Осталось предъявить расстановку ровно шести кругов без наложений — это и делает кнопка «Расставить равномерно» при шести кругах на кольце: углы $0^\circ,60^\circ,120^\circ,180^\circ,240^\circ,300^\circ$. Каждая пара соседей отстоит ровно на $60^\circ$ — угловое условие выполнено с равенством (круги касаются друг друга, но не налегают). Шесть кругов действительно помещаются.
$K(2)=6$.
Обратите внимание, что оптимальная расстановка на плоскости не просто существует — она по сути единственна (с точностью до поворота всего кольца) и совершенно жёсткая: у шести кругов в правильном шестиугольнике нет никакого зазора, каждое касается сразу двух соседей. Именно эта жёсткость и делает доказательство элементарным. В пространстве, как выясняется дальше, жёсткости уже нет — и именно поэтому там всё оказалось так трудно.
В $\R^3$ рассуждение начинается совершенно так же. Направление от центра шара к центру каждого касающегося его шара — это единичный вектор; два таких направления соответствуют не налегающим друг на друга шарам ровно тогда, когда угол между векторами не меньше $60^\circ$ — то же самое условие, тот же вывод $4\sin(\theta/2)\ge2$, только теперь речь о точках на сфере направлений, а не на окружности.
Угол $60^\circ$ между направлениями означает, что вокруг каждого направления можно описать сферическую «шапочку» углового радиуса $30^\circ$ (половина от $60^\circ$), и шапочки разных шаров не перекрываются. Площадь такой шапочки на единичной сфере равна $2\pi(1-\cos30^\circ)\approx0{,}842$, а площадь всей сферы — $4\pi\approx12{,}566$. Простое деление площадей даёт:
То есть площадной довод сразу же даёт верхнюю оценку $K(3)\le14$ — и застревает на этом. В отличие от плоского случая, здесь он не может отличить $14$ от $13$ от настоящего ответа, $12$ — потому что площадной аргумент не учитывает, что шапочки должны ещё и укладываться на сфере геометрически согласованно, а не просто «по площади».
Более того, двенадцать шаров вокруг одного действительно помещаются — и не одним способом. Можно расставить их по вершинам правильного икосаэдра: тогда между соседними шарами остаётся заметный зазор, ни одна пара из двенадцати не касается друг друга. А можно — как в кубической или гексагональной плотнейшей упаковке шаров (той самой, из гипотезы Кеплера) — расставить их так, что каждый касается ещё четырёх своих соседей среди этих же двенадцати. Оба варианта дают ровно $12$, но это уже не одна жёсткая конфигурация, как правильный шестиугольник на плоскости, а целое семейство разных расстановок с ощутимым люфтом. Именно этот люфт и подпитывал уверенность Грегори: раз есть свободное место, кажется, что тринадцатый шар должен влезть — хотя на самом деле не влезает.
Из-за этого простого аргумента с суммой углов, который решил всё на плоскости за пять строк, в пространстве не хватает. Строгое доказательство того, что тринадцатый шар не помещается ни при какой расстановке, дали только в 1953 году Курт Шютте и Бартел ван дер Варден — спустя 259 лет после спора Ньютона и Грегори. Более простое доказательство нашёл в 1956 году Джон Лич.
$K(3)=12$ — Ньютон был прав.
Контактное число $K(n)$ имеет смысл в любой размерности $n$, но точно оно известно на удивление редко — метод площадей и жёсткие конструкции, которые сработали для $n=2$ и (с большим трудом) для $n=3$, дальше перестают быть достаточными сами по себе.
Для размерностей $8$ и $24$ ответ известен точно не случайно: именно там на решётках $E_8$ и Лича достигается не только рекордное контактное число, но и (что доказала Марина Вязовская с соавторами в 2016–2017 годах, применив методом линейного программирования Дельсарта специально построенные «магические функции» из теории модулярных форм) самая плотная возможная упаковка шаров — тот же метод одновременно закрывает обе задачи. За решение задачи об упаковке шаров в размерностях 8 и 24 Вязовская получила Филдсовскую медаль в 2022 году.
А вот $K(5)$, $K(6)$ и $K(7)$ до сих пор точно неизвестны — только оценки сверху и снизу, зазор между которыми пока не закрыт. Задача, которую можно честно и полностью решить для шаров на столе, за пределами первых нескольких размерностей остаётся открытой областью исследований прямо сейчас.