Новая нижняя граница для упаковки 17 квадратов: 4.5058
Another Better Lower Bound for N=17 Square Packing
В блоге представлено улучшение нижней границы для задачи упаковки 17 единичных квадратов в минимальный квадрат. Автор использует линейное программирование для подбора весов точек, которые гарантируют, что любой единичный квадрат содержит суммарный вес не менее 1. Это позволяет доказать, что сторона квадрата не может быть меньше 4.5058. Предыдущая граница, полученная Сэмом Бернсом с помощью ChatGPT, составляла 4.4811. Новый результат использует 168 точек на сетке 29x29 и веса, округлённые до рациональных дробей. Программа для проверки сертификата прилагается.
Моя главная претензия к Сэму Бернсу в том, что его результат действительно заслуживал хорошей графики!
- dooglius
Отвечая на пару комментариев здесь: картинки или новой раскладки квадратов нет, потому что это _верхние_ границы для задачи. Лучшая известная раскладка, т.е. лучшая известная верхняя граница, не изменилась.
- scuppernong
Некоторые из этих точечных конфигураций отдалённо напоминают фигуры Хладни (https://chalkdustmagazine.com/regulars/on-the-cover/cover-ch...), возникающие при колебаниях квадратной мембраны. Ортогонально, интересно, обобщаются ли эти конфигурации, чтобы дать нижние границы для N = n^2 + 1.
- teddyh
Ни на одном из изображений нет квадратов.