Круги в круге

Радиус равен 3, а «оптимальная картинка» выглядит именно так, как вы ее себе, скорее всего, и представили (рис. 1).

Рис. 1

Удобно избавиться от понятия «наложение», перейдя от этой задачи к такой:
Рассмотрим вместо кругов только их центры. В круг какого наименьшего радиуса можно их все уместить?

Рис. 2

В «оптимальной картинке» все центры являются вершинами и центром правильного шестиугольника со стороной 2 (рис. 2). При этом расстояние между любыми двумя вершинами и центром такого шестиугольника тоже равно 2, поэтому все точки лежат в круге радиуса 2. Нужно обосновать, что все эти точки нельзя уместить в круг меньшего радиуса. Для этого попробуйте рассмотреть случаи, сколько именно (из шести отличных от центра) точек образуют выпуклый многоугольник.

Будем действовать методом «от противного». Предположим, что шесть точек с попарным расстоянием 2 (или большим двух), удалось поместить в круг радиуса R < 2. Сделаем гомотетию с коэффициентом 1/R. Тогда этот круг станет единичным.

Гомотетия (от греч. homos — равный, одинаковый, взаимный, общий и thetos — расположенный) — такое преобразование плоскости, при котором каждой точке М ставится в соответствие некоторая точка М', лежащая на ОМ, где О — фиксированная точка, причем отношение ОМ' : ОМ = k (коэффициент гомотетии) одинаково для всех точек М. При гомотетии каждая фигура переходит в подобную, а все расстояния между точками изменяются ровно в k раз.

Ниже мы докажем, что если 6 точек лежат в единичном круге, то расстояние между какими-то двумя из них не превышает 1. Это означает, что до гомотетии расстояние между какими-то двумя точками не превышало R, то есть было меньше 2. Середина отрезка между этими двумя точками находится от концов отрезка на расстоянии, меньшем 1, то есть внутри каждого из единичных кругов с центрами в этих концах. Иными словами, эти единичные круги накладываются. Противоречие.

Лемма. Если 6 точек лежат в единичном круге, то расстояние между какими-то двумя из них не превышает 1.

Доказательство.

1. Сперва отметим, что если какая-то из шести точек (обозначим её X) лежит внутри остальных (математики говорят: «внутри выпуклой оболочки остальных»), то расстояние от нее до какой-то из остальных не больше 1.

Действительно, если в выпуклую оболочку входит всего две точки, то все остальные точки лежат на отрезке. Длина этого отрезка не больше 2, поэтому если на него поставить точку, то расстояние от нее до какого-то из концов отрезка будет не больше 1.

Если же в выпуклой оболочке не менее трех точек, то всегда можно выбрать три из них, скажем, A, B, C таким образом, что X принадлежит выпуклой оболочке точек A, B, C, то есть лежит в треугольнике ABC. Но любая точка в этом треугольнике лежит в единичном круге с центром в одной из вершин треугольника (см. рис. 3).

Рис. 3. Из каждой вершины треугольника проводим круг радиуса 1. Каждая точка треугольника покрашена хотя бы одним цветом, то есть покрыта хотя бы одним из кругов

Таким образом, для этого случая (одна из шести точек лежит внутри выпуклой оболочки остальных) утверждение уже доказано.

2. Теперь предположим, что выпуклая оболочка включает все 6 точек.

Если какая-то из них (скажем, A) не лежит на границе круга, то ее можно переместить на границу так, что расстояние до остальных точек не уменьшится. Это можно сделать, например, проведя через A хорду, отделяющую A от остальных точек, а затем сдвинув A на граничную окружность перпендикулярно к этой хорде (рис. 4).

Рис. 4

Пояснение к рис. 4. B и C — ближайшие к A точки выпуклой оболочки (будем считать, что они уже НА окружности, хотя это не так уж важно). Тогда угол BAC меньше 180°. Это означает, что через A можно провести хорду FG так, что точки B и C окажутся по одну сторону от нее.

А еще можно провести AH перпендикулярно FG и сдвинуть точку A в точку H. Поскольку углы BAH и CAH оказались больше, чем FAH и GAH, то оба они тупые, а значит, в треугольниках BAH и CAH против них лежит наибольшая сторона. Иначе говоря, BH > BA и CH > CA. То есть при сдвиге A в H расстояния до точек B и C увеличились.

Наконец, если все точки лежат на единичной окружности, то они делят ее на 6 дуг, поэтому длина наименьшей из дуг не больше, чем 1/6 длины окружности, то есть не больше 2π/6. Это значит, что величина центрального угла этой дуги также не превышает 2π/6, а значит, расстояние между двумя точками, являющимися концами этой дуги, не больше 2sin(π/6) = 1.

Эта задача является примером огромного класса так называемых «минимаксных» задач вычислительной геометрии. В минимаксных задачах ищется наибольшее возможное значение какой-то величины, которая сама определена как наименьшее значение другой величины. В нашем случае минимаксная задача (к которой мы свели исходную) была такой: сначала среди всех 15 попарных расстояний между шестью точками в единичном круге выбирается наименьшее, а затем ищется такая конфигурация шести точек, для которой это расстояние будет максимальным из возможных.

Приведенное нами утверждение и его доказательство принадлежат замечательному американскому математику Рональду Грэхему (Ronald Graham), они опубликованы в 1968 году. Грэхем доказал даже более общую оценку для наименьшего расстояния d между какими-то из k точек, лежащих в единичном круге. Эта оценка имеет вид

    d ≤ max(1, 2 sin π/k)

(то есть d не превышает наибольшего из двух чисел — единицы и удвоенного синуса). Оценка Грэхема является оптимальной для 2 ≤ k ≤ 7, то есть существуют картинки, для которых достигаются значения из правой части этого неравенства. Для больших значений k указанная оценка неточна, поскольку она дает d ≤ 1, а на самом деле наибольшее из возможных значений минимального расстояния между точками строго меньше 1.

Естественное обобщение нашей задачи — поиск кругов наименьшего радиуса, в которые можно поместить N единичных кругов (или, что то же самое, поиск решения минимаксной задачи об N точках в единичном круге). В этом поиске усилия математиков сконцентрировались на двух направлениях — компьютерном моделировании и доказательствах оптимальности. Ниже на рис. 5 показаны несколько очевидных оптимальных картинок.

Рис. 5

Оптимальность первых трех из них следует из приведенного выше результата Р. Грэхема. Оптимальность последней (для 8 кругов) была доказана в 1963 году голландцем Boele L. J. Braaksma в его диссертации под труднопроизносимым названием «Асимптотические расширения и аналитические продолжения для одного класса интегралов Барнса». Следующее продвижение, а также оптимальность вот такой вот картинки (рис. 6) с двумя внутренними кругами (для 10 кругов)

Рис. 6

было получено немцем U. Pirl в 1969 году. Оптимальность аналогичной картинки для 11 кругов доказана еще на 25 лет позже, а для 12, 13 и 19 кругов — еще позже (последний из результатов — в 2003 году).

И... всё. Остальные результаты об упаковке кругов в круг на сегодняшний день находятся в состоянии «оптимальность предполагается, но не доказана». Так что просто полюбуйтесь на картинки (рис. 7) с доказанной оптимальностью (N = 12 и N = 19) и оцените: всего каких-то 15 лет назад это была терра инкогнита, обе задачи еще ждали своего решателя.

Рис. 7

А следующие две картинки (для N = 14 и N = 15 соответственно) являются этой самой «инкогнитой» и сейчас (рис. 8). Дерзайте.

Рис. 8

См. также:
1) Circle packing in a circle («Упаковка кругов в круг»). Достаточно детальная статья английской Википедии.
2) Circles in Circles. Страничка Эрика Фридмана, откуда мы позаимствовали большую часть иллюстраций. Там же на соседних страницах packing center рассказано о других задачах упаковки.
3) K. A. Dowsland, M. Gilbert, G. Kendall. A local search approach to a circle cutting problem arising in the motor cycle industry (PDF, 346 Кб). Статья в научном журнале Operational Research Society — международного сообщества, занимающегося исследованием операций, то есть научной дисциплиной, чья основная задача — обоснование оптимальности применения каких-либо научных достижений на практике.
В статье объясняется, как можно оптимизировать изготовление «звездочек» и других профилированных колёс (для зубчатых передач и др.) при производстве велосипедов и мотоциклов. С точки зрения математики — абсолютно ничего нового, но связь с практикой очень забавна. Интересно, появится ли когда-нибудь подобная статья для домохозяек — об оптимизации раскладывания котлет на сковородке?