Задача про пакування куль

Розміщення плодів апельсину

Задача про пакування куль — задача комбінаторної геометрії про розміщення однакових куль в евклідовому просторі без їх взаємного перетинання. Типова постановка задачі наступна: знайти спосіб розташування куль в просторі, при якому кулі займають найбільшу частину цього простору.

Close packing box.svg
Найбільш ефективний спосіб пакування кіл різного розміру на площині не є очевидним

Історія задачіРедагувати

В кінці 1500-х років сер Волтер Рейлі попросив англійського математика Томаса Герріота придумати більш ефективний спосіб укладання гарматних ядер на кораблях британського військового флоту. Герріот розповів про це завдання астроному Йогану Кеплеру. Кеплер припустив, що найбільш щільний спосіб упаковки сфер вже і так застосовується — при укладанні гарматних ядер і фруктів: перший шар викладається кулями поруч одна з одною у вигляді шестикутника, другий в заглиблення на стиках куль нижнього шару і т.д. У великій тарі при такому варіанті укладання максимальна щільність буде близько 74%:

 

Кеплер вважав, що це найщільніший варіант упаковки, але не зміг цього довести. Гіпотезу про найщільніше пакування куль однакових розмірів у тривимірному просторі при їх пірамідальному впорядкуванні одна відносно одної Кеплер виклав в 1611 році в своєму дослідженні «Про шестикутні сніжинки».

В 1694 році дискусію щодо пакування куль продовжили Девід Грегорі та Ісаак Ньютон в Кембриджі. Грегорі вважав, що існує таке пакування куль, коли кожна з куль може дотикатись 13 інших, Ньютон обстоював число 12.

Гіпотеза Кеплера залишалася недоведеною протягом декількох століть і потрапила до списку з 23 невирішених математичних задач, складеного у 1900 році Давидом Гільбертом. В 1998 році математик Томас Гейлс запропонував складне доведення цієї гіпотези, що базувалось на простому переборі всіх можливих варіантів (варіанти обчислювались за допомогою комп'ютера), але доведення не є математично обґрунтованим[1].

Пакування кіл на площиніРедагувати

1940 році було доведено, що у двовимірному евклідовому просторі найкращим заповненням є розміщення центрів кіл в вершинах паркету, утвореного правильними шестикутниками, в якому кожне коло оточене шістьма іншими.

Пакування куль у тривимірному просторіРедагувати

1958 року математик і популяризатор науки Гарольд Коксетер висловив зауваження, що найщільнішу пакування ще не знайдене: 12 куль можна розташувати так, що всі вони будуть дотикатись центральної кулі, і зовсім трохи не вистачає, щоб до цих 12 можна було додати 13-ту кулю. Порожнечі в розташуванні 12 куль навколо центральної кулі наводять на думку про те, що при певному неправильному пакуванні щільність може виявитися вищою за 0,74. Можливість такого пакування не доведена, також не доведено, що необхідний дотик з 12 сусідніми кулями.

Гіпотеза Коксетера спонукала проведення ряду експериментів з кулями, упакованими випадковим чином, отримані результати показали, що випадкові упаковки відповідають щільностям у діапазоні від 0,59 до 0,63, що є далеким до 0,74 для щільності впорядкованого пакування.

Пакування в багатовимірних просторахРедагувати

Пакування на площині і в тривимірному просторі досить легко уявити, але існують також задачі пакування і для просторів більшої розмірності.

Задачі для пакування куль у просторі розмірності 8 вирішила в 2016 році українська математичка Марина В'язовська[2]. Розв'язання В'язовською восьмивимірного випадку задачі виявилось «приголомшливо простим» — всього 23 сторінки в порівнянні з 300-та сторінками тексту та 50 000 рядків програмного коду при доведені гіпотези Кеплера для тривимірного простору.

ПриміткиРедагувати

ПосиланняРедагувати