Упакування квадратів — це задача пакування, ціллю якої є визначення кількости конгруентних квадратів, які можна впакувати у якусь більшу форму, зачасту квадрат або круг.
У квадрат Упакування квадратів в квадрат — це задача визначення максимальної кількости одиничних квадратів (квадратів з довжиною сторін 1), які можна впакувати усередині більшого квадрата з довжиною сторін . Якщо є цілим числом, рішення — це , але точна, або навіть асимптотна, кількість незаповнених пропусків для довільного нецілого числа є відкритим питанням.
Найменше значення , яке дозволяє упакування одиничних квадратів відоме, якщо є ідеальним квадратом (в цьому випадку воно дорівнюватиме ), а також для 2, 3, 5, 6, 7, 8, 10, 13, 14, 15, 24, 34, 35, 46, 47 і 48. Для більшости з цих чисел (окрім лише 5 та 10), упаковка - натуральна, з вирівняними по осям квадратами і — , де — це функція ceiling (округлення вгору). На малюнку показані оптимальні упакування для квадратів з довжиною 5 і 10, дві найменші кількості квадратів, для яких оптимальне пакування включає нахилені квадрати.
Найменший невирішений випадок — це . Відомо, що 11 одиничних квадратів неможливо упакувати в квадрат з довжиною сторін, меншою . В порівнянні, найщільніше відоме упакування 11 квадратів є всередині квадрата з довжиною сторін, що приблизно дорівнює 3.877084, яку знайшов Волтер Трамп.Версія 2000 перелічила цю довжину як 3.8772; більш щільне обмеження, зазначене тут, походить від
Найменший випадок, де найкраще відоме упакування включає квадрати, нахилені під трьома різними кутами — це . Він був виявлений у 1998 Джоном Бідвелом, студентом бакалаврату в University of Hawaiʻi, і має довжину сторін .
Нижче показані мінімальні рішення для значень до ; випадок залишається невирішеним: Кількість одиничних квадратів Мінімальна довжина сторін великого квадрата1122324252.707…63738393103.707…113.877… ?124
Асимптотичні результати
Для більших значень довжини сторін , точне число одиничних квадратів, які можна упакувати в квадрат залишається невідомим. Упакувати сітку одиничних квадратів , вирівняних по осі завжди можливо, але це може залишити більшу область, приблизно , непокриту та витрачену. Натомість, Пал Ердеш і Рональд Грем показали, що для різного пакування за нахиленими одиничними квадратами, марно витрачений простір можна суттєво зменшити до (тут написано у нотації маленького o). Згодом, Грем і Фан Чун більше зменшили марно витрачений простір до . Однак, як довели Клаус Рот і Боб Воган, усі рішення мають марто витратити принаймні простору. Зокрема, коли — це напівціле число, марно витрачений простір є щонайменше пропорційним його квадратному кореню. Точна асимптотична швидкість зростання марно витраченого простору, навіть для напівцілих довжин сторін, залишається відкритою проблемою.
Деякі кількості одиничних квадратів ніколи не є оптимальними кількостями у пакуванні. Зокрема, якщо квадрат розміру дозволяє упакування одиничних квадратів, тоді повинно бути так, що і що упакування з одиничних квадратів також можливе.
У коло Упакування квадратів у коло — це пов’язана проблема упакування n одиничних квадратів у коло з найменшим можливим радіусом. Для цієї проблеми, гарні рішення відомі для значень n до 35. Ось мінімальні відомі рішення для n до (хоча лише випадки і відомі як оптимальні):
Кількість квадратівРадіус кола1234561.688…781.978…910112.214…12
В інші форми Упакування квадратів в інші форми має високу обчислювальну складність: тестування чи певне число одиничних квадратів паралельних по осі можуть поміститися у певний многокутник є NP-повним. Воно залишається NP-повним навіть для простого многокутника (без отворів), який є ортогонально опуклим, зі сторонами паралельними до осей, і з напівцілими координатами вершин.
Див. також Упакування кол в квадрат Квадрування квадрата Упакування прямокутників Задача про переміщення канапи
Примітки
Посилання