§ 2. Задачи о плотнейшем заполнении плоскости кругами и о редчайшем покрытии плоскости кругами

Положим на большой стол некоторое число равных монет. Естественно встает вопрос: как надо расположить монеты, чтобы на столе поместилось возможно большее число их?

Двойственная задача читается следующим образом: мы хотим покрыть большую плоскую область равными круглыми бумажными салфетками. Как надо расположить их, чтобы возможно меньшим числом салфеток покрыть всю область?

Естественно, что самое благоприятное размещение кругов существенно зависит от величины и формы области, и нельзя ожидать, что найдется общий рецепт, позволяющий определить искомое размещение для любой области. Поэтому здесь можно стремиться лишь к определению асимптотического размещения кругов для больных областей.

Понятие плотности позволяет дать точные формулировки поставленных выше вопросов:

1. Чему равна верхняя грань плотности системы равных иеперекрывающихся кругов и для какой системы кругов достигается эта верхняя грань?

2. Чему равна нижняя грань плотности системы равных кругов, целиком покрывающих плоскость и для какой системы кругов достигается эта нижняя грань?

Ответы на эти вопросы дают следующее теоремы, доказательства которых будут приведены ниже:

Если d — плотность любой системы равных не перекрывающихся кругов, то

Если D плотность системы равных кругов, полностью покрывающих плоскость, то

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

Выражаясь не совсем строго, но наглядно, можно сказать, что в силу неравенств (1) и (2) равными неперекрывающимися кругами можно покрыть не более 90,69° 0 плоскости и что общая плошадь системы равных кругов, которыми можно полностью покрыть плоскость, не может быть меньше 120,9° 0 площади всей плоскости.

Приведем теперь еще несколько других формулировок тех же самых задач.

Задача о плотнейшем заполнении эквивалентна следующей. Как расположить в заданной области большое (но фиксированное) число точек так, чтобы каждая точка была удалена от других возможно дальше, т. е. чтобы кратчайшее расстояние между двумя из наших точек было возможно больше? Или наоборот — пусть нам требуется посадить в большом саду возможно больше деревьев так, чтобы расстояние между каждыми двумя деревьями было не меньше заданной величины (рис. 55).

Задачу о редчайшем покрытии плоскости кругами можно сформулировать так. Как расположить в заданной области большое число точек так, чтобы каждая точка области лежала возможно ближе к какой-то из наших точек, т. е. чтобы наибольшее расстояние от точки области до самой близкой к ней из наших точек было возможно меньшим? Или наоборот, пусть мы хотим разместить в пустыне возможно меньшее число оазисов так, чтобы расстояние от каждой точки пустыни до ближайшего оазиса не превосходило заданного расстояния (рис. 56).

Точки в обеих этих задачах должны располагаться в вершинах решетки из равносторонних треугольников, т. е. в вершинах решетки, отвечающей вырожденному правильному многограннику [3, 6].

Рис. 55.

Новые формулировки наших задач приводят к следующим эквивалентным неравенствам (1) и (2) теоремам, относящимся к системам точек плоскости:

Если среднее число точек системы равно А, а расстояние между каждыми двумя из этих точек не меньше о, то

Если среднее число точек системы равно А, а расстояние от каждой точки плоскости до ближайшей к ней точки системы не превосходит , то

Рис. 56.

Рис. 57.

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

На рис. 57 изображена редчайшая насыщенная система кругов и отвечающее ей редчайшее покрытие плоскости кругами.