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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук
Розміщення плодів апельсину

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

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 рядків при доведені гіпотези Кеплера для трьохмірного простору.

Примітки[ред.ред. код]

Посилання[ред.ред. код]