Задача про пакування куль задача комбінаторної геометрії про розміщення однакових куль в евклідовому просторі без їхньог

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

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

Попередник	^d
Наступник	невідомо
Підтримується Вікіпроєктом
Задача про пакування куль у Вікісховищі

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

Загальна характеристика

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

Історія задачі

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

${\frac {\pi }{3{\sqrt {2}}}}\simeq 0.74048$

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

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

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

Пакування кіл на площині

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

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

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

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

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

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

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

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

Див. також

Примітки

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

Посилання

Яськов Г. Н. Упаковка большого числа конгруэнтных шаров в цилиндре^{[недоступне посилання з серпня 2019]}(рос.)

[1] Компьютер проверил доказательство гипотезы Кеплера [ 7 квітня 2016 у Wayback Machine.] (рос.)

[2] Knudson, Kevin (29 березня 2016), , Forbes, архів оригіналу за 28 листопада 2019, процитовано 7 квітня 2016