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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до навігації Перейти до пошуку
Задача про пакування куль
Зображення
Попередник circle packingd
CMNS: Задача про пакування куль у Вікісховищі
Розміщення плодів апельсину
Найбільш ефективний спосіб пакування кіл різного розміру на площині не є очевидним

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

Історія задачі[ред. | ред. код]

Наприкінці 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 рядків програмного коду під час доведення гіпотези Кеплера для тривимірного простору. За рішення удостоєна низки міжнародних математичних нагород, та, у 2022 році, Медалі Філдса.

У 2017 році Вязовська стала співавторкою розв'язку пакування куль в розмірності 24.

Див. також[ред. | ред. код]

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

  1. Компьютер проверил доказательство гипотезы Кеплера [Архівовано 7 квітня 2016 у Wayback Machine.] (рос.)
  2. Knudson, Kevin (29 березня 2016). Stacking Cannonballs In 8 Dimensions. Forbes. Архів оригіналу за 28 листопада 2019. Процитовано 7 квітня 2016. 

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