uzluga.ru
добавить свой файл
1 2 3 4

Упаковка шаров

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

Н. ДЖ.А.СЛОЭН

ПРЕДСТАВИМ, что некая фирма по производству шарикоподшипников получила заказ: отправить в иностранный порт столько одинаковых шариков для подшипников, сколько удастся погрузить на зафрахтованные суда в условленный день. Шарики приготовлены к отправке, однако в назначенный день в порту оказалось лишь одно судно, готовое принять груз. Член команды, ответственный за погрузку, объяснил представителю фирмы, что во избежание чрезмерной осадки судна шарики не должны занимать более трех четвертей объема трюма. Это замечание не смутило отправителя. «Вашему судну ничто не грозит, — ответил он уверенно, — заполняйте трюм доверху». Что делать ответственному за погрузку — верить или не верить клиенту?

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

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

Многие люди, потратив несколько минут на эксперименты с апельсинами или бильярдными шарами, приходят к ошибочному выводу, что проблема тривиальна. Уложим три шара на плоской поверхности так, чтобы их центры образовали равносторонний треугольник, а сами они касались друг друга. Затем будем подкладывать к ним другие шары так, чтобы каждый новый касался двух уже уложенных. Так получится первый слой шаров. Затем уложим второй слой, помещая каждый новый шар в «глубокую яму», или углубление, образовавшееся в центре каждой треугольной группы шаров первого слоя. В законченном виде второй слой не отличается от первого, он только сдвинут в горизонтальной плоскости. Если и следующие слои

ГРАНЕЦЕНТРИРОВАННАЯ КУБИЧЕСКАЯ упаковка шаров, которую можно часто увидеть на прилавках фруктовых магазинов или в пирамидах пушечных ядер на военных мемориалах, считается плотнейшей упаковкой шаров в трехмерном пространстве. Однако, несмотря на многие годы усилий, доказать, что ее плотность максимальна, до сих пор не удалось. Каждый шар в этой упаковке касается 12 других; доказательство того, что это максимальное число касаний, было получено лишь в 1874 г. Если центр одного из шаров фиксирован, то множество всевозможных вращений и отражений, меняющих местами 12 окружающих шаров, образует группу, которая называется группой симметрии этой упаковки. Группа симметрии гранецентрированной кубической упаковки состоит из 48 элементов. Их легче всего сосчитать, если рассматривать центры шаров как вершины изображенного справа многогранника, который называется кубооктаэдром. Каждая из шести квадратных граней кубооктаэдра может стать передней гранью после подходящего вращения фигуры вокруг зеленой или синей оси (А—Е). Каждое множество четырех сфер, образующих квадратную грань (скажем, четвертую), при вращении всей фигуры вокруг красной оси может оказаться в одной из четырех конфигураций (D1—D4). Наконец, каждую конфигурацию (например, третью) можно отразить в вертикальной плоскости и получить новую конфигурацию (D3a, D3b). Следовательно, общее число элементов группы симметрии равно 6x4x2, т.е. 48. Аналогичная группа симметрии, описывающая вращения и отражения плотной упаковки шаров в 24-мерном пространстве, открытой Дж. Личем из Университета г. Глазго, оказалась полезной в математической теории конечных групп.

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

К сожалению, математически не доказано, что это максимально достижимая плотность. Из полученных до сих пор верхних оценок плотности наименьшая была найдена в 1958 г. К. А. Роджерсом из Бирмингемского университета; он доказал, что никакая упаковка шаров не может иметь плотность большую чем —0,7796. Однако этот результат не слишком поможет тому, кто ищет оптимальный способ упаковки шариков для подшипников.





УПАКОВКА ШАРОВ_73



Дело в том, что в доказательстве Роджерса не предлагается никакой упаковки шаров, плотность которой была бы близка к найденной оценке. Более того, сам Роджерс в статье, где сообщалось о полученном доказательстве, заметил: «многие математики верят, а все физики знают», что правильный ответ составляет около 74%. За четверть века, прошедшие с тех пор, ничего не изменилось, и задача о плотной упаковке шаров, такая простая на вид и столь трудная по существу, остается одной из важных нерешенных проблем в математике.

КОНФИГУРАЦИИ плотной упаковки шаров изучаются уже многие годы. Отчасти это объясняется тем, что они тесно связаны с изучением свойств твердых тел и жидкостей. Так, например, физические свойства многих кристаллических материалов можно описывать, по крайней мере в первом приближении, исходя из модели кристалла как системы огромного числа твердых шаров (изображающих атомы) в плотной упаковке. Не менее важное применение эта модель находит при исследовании порошков и пористых материалов.

Если экспериментальное изучение упаковок шаров важно для понимания свойств некоторых физических систем, то имеются достаточно веские ПрИЧИ-

^-г



ны и для чисто математического изучения идеально плотных упаковок. Тот факт, что до сих пор в отношении ни одной известной упаковки не доказано, что она самая плотная, говорит о том, что математическое исследование обычного трехмерного евклидова пространства еще далеко от завершения. Кроме того, математики обобщили понятие шара и задачу об упаковке шаров на многомерные пространства и рассматривают объекты, называемые w-мерными шарами, алгебраическое описание которых напоминает алгебраическое описание обычных шаров. Оказалось, что поиск плотной упаковки шаров в w-мерном пространстве математически эквивалентен разработке конечного множества закодированных цифрами сообщений, которые допускают их передачу без искажений при минимальных затратах энергии. Более того, найденные в последние годы плотные упаковки в пространствах 24 и более измерений привели к крупным открытиям в самой математике — в той ее области, которая называется теорией групп.

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

1694 г. эта задача (в случае трехмерного пространства) стала предметом получившего широкую известность диспута между Исааком Ньютоном и шотландским астрономом Джеймсом Грегори. Ньютон утверждал, что число касаний равно 12, и для описанной выше гранецентрированной кубической упаковки это действительно так (см. рисунок на с. 73). Грегори, по-видимому, не соглашался, настаивая на том, что можно «втиснуть» еще один дополнительный шар, хотя он и не мог это доказать.

ПО МНЕНИЮ Г.СМ. Коксетера из Университета г. Торонто, Грегори, скорее всего, вообразил, что 12 окружающих шаров можно так передвинуть по центральному шару, чтобы все просветы между ними скопились в одном месте и туда вошел бы еще один шар. И действительно, как легко показать, телесный угол, под которым один из окружающих шаров виден из центра центрального шара, составляет меньше 1/13 полного телесного угла, и, таким образом, если судить только по объему, вокруг центрального шара в самом деле могли бы уместиться 13 шаров. Однако часть полного телесного угла с неизбежностью приходится на просветы между окружающими шарами. Вопрос о числе касаний был разрешен лишь в 1874 г. Как показал Р. Хоп-пе, прав был Ньютон.

Вторая важная задача, связанная с упаковкой шаров, — это так называемая задача о редчайшем покрытии: как наиболее экономно расположить одинаковые шары в пространстве, чтобы каждая точка пространства оказалась внутри или на границе хотя бы одного из них? В отличие от задачи о плотней-шей упаковке, в которой речь шла о неперекрывающихся шарах, в этой задаче шары обязательно перекрываются. Возможен такой способ покрытия пространства шарами: рассмотрим какую-нибудь упаковку шаров и затем «раздуем» каждый шар так, чтобы заполнились все пустоты исходной упаковки. Однако оказалось, что в общем случае «раздутие» шаров самой плотной упаковки не приводит к оптимальному решению задачи о покрытии. Так, например, в трехмерном пространстве наилучшим принято считать покрытие шарами с центрами в узлах так называемой объемноцентрированной кубической решетки. Но если расположить в этих же узлах центры одинаковых неперекрывающихся шаров, то получится упаковка, которая уже не будет столь плотной, как другие известные упаковки шаров, например рассмотренная выше гранецентрированная кубическая. Правда, и сама гипотеза о том, что объемноцентрированная ку-

УПАКОВКИ «ШАРОВ» можно рассматривать не только в трехмерном, но также и в одномерном или двумерном пространствах. В размерности 1 шарами являются прямолинейные отрезки единичной длины с центрами в целых точках. Они покрывают 100% прямой, и каждый из них касается двух других. Очевидно, что это наи-плотнейшая возможная упаковка; она называется Z\ На плоскости шарами являются круги; известны три представляющие интерес упаковки. В упаковке Z2 центры кругов расположены во всех точках с целыми координатами; в упаковке D2 центры расположены в тех же точках через одну в шахматном порядке. Если изменить масштаб на координатных осях и повернуть их на 45°, то упаковка Z2 перейдет в D2, следовательно, эти упаковки эквивалентны. Чтобы найти их плотность, нужно вычислить, какую долю площади квадрата покрывают круги или их части (т.е. сосчитать площадь закрашенной части квадрата); она равна /4, или примерно 0,7854 (слева). Плотнейшей упаковкой кругов на плоскости является гексагональная решетчатая упаковка L2. Круговые секторы в этой упаковке покрывают ttV3/6 каждого равностороннего треугольника; следовательно, плотность этой упаковки равна приблизительно 0,9069 (справа).







бическая решетка дает решение задачи о покрытии, тоже не доказана.

Почему же так трудно решить проблему упаковки шаров в трехмерном пространстве? Рассмотрим снова гра-нецентрированную кубическую упаковку. Поскольку требуется максимизировать такую величину как плотность, следует считать число шаров неограниченным. Если, скажем, убрать из исходной упаковки миллион шаров, ее плотность фактически не изменится. Но изъятие каждого шара из исходной упаковки приводит к новой упаковке. Таким образом, если бы удалось доказать, что гранецентрированная кубическая упаковка оптимальна (как многие полагают), то одновременно была бы доказана оптимальность бесконечного множества других упаковок!

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

Предположим, что к этой конфигурации добавляются по одному новые шары, причем так, чтобы всегда, когда это возможно, образовалась новая тетраэдральная конфигурация. Если бы эту процедуру можно было продолжать до бесконечности, то полученное в результате расположение шаров имело бы наибольшую возможную плотность, поскольку все тетраэдральные комплекты были бы упакованы плот-нейшим образом. Найденная Роджерсом верхняя оценка плотности получена на основе именно таких соображений: прямое вычисление по формулам сферической тригонометрии показывает, что четыре неперекрывающихся шара с центрами в вершинах тетраэдра могут заполнить примерно 0,7796 его объема (точный результат равен у[2 [3 arccos (1/3) — 7г]). Но, к сожалению, плотно прилегающими друг к другу тетраэдрами нельзя «выложить» все пространство. Стратегия упаковки шаров в тетраэдральные комплекты до тех пор, пока это возможно (такую стратегию можно было бы назвать «жадным» алгоритмом), приводит в конце концов к неудачному ходу. На определенном шаге процедуры возникает такая конфигурация шаров, которая уже неспособна «поглотить» очередной шар без увеличения просвета между ними. Таким образом, хотя «жадный» алгоритм и порождает оптимальную упаковку шаров в небольшой области, размеры которой не превосходят, скажем, нескольких их диаметров, в конечном счете он приводит к менее плотной упаковке, чем гранецентрированная кубическая.

ДЛЯ ТОГО чтобы продвинуться в решении трех указанных задач, математики подкрепляют свою геометрическую интуицию аналитическим представлением шаров в прямоугольной системе координат. Хорошо известно, что любую точку на плоскости можно задать двумя координатами: х — по горизонтальной оси и у — по вертикальной. Обычно точка плоскости записывается в виде упорядоченной пары (х, у). Так, например, (3,4) — это точка на плоскости, находящаяся на три единицы правее начала координат вдоль оси х и на четыре единицы выше вдоль оси у.

Расстояние между этой точкой (3, 4) и любой другой точкой (х, у) можно сосчитать по теореме Пифагора: квадрат искомого расстояния равен сумме квадратов расстояний вдоль оси х и вдоль оси у, т.е. (х — З)2 + (у — 4)2. Так как окружность, по определению, есть множество всех точек на плоскости, равноудаленных от некоторого центра, скажем (а, Ь), то любая точка (х, у) окружности должна удовлетворять уравнению (х — а)2 + (у - b)2 = R , где R — радиус этой окружности. Если радиус равен 1, а центр находится в нача-






следующая страница >>