Плотнейшая упаковка кругов без контакта

[melnikoff]

В квадрат площадью 16 бросили 37 точек. Докажите, что можно нарисовать круг диаметра 1, в котором находятся 2 из этих точек.
Задача отсюда.

Моё решение:
Начнём с некоторого упрощения. Определим круг по-своему: Круг – это геометрическое место точек плоскости, расстояние от которых до заданной точки, называемой центром круга, меньше заданного неотрицательного числа $R$.

Опишем вокруг каждой точки круг радиуса 1/2 с центром в этой точке. Если какие-либо 2 круга пересекаются, то расстояние между их центрами меньше 1 и, следовательно, можно нарисовать круг с единичным диаметром, которому эти два центра принадлежат. Расширим наш квадрат на 1/2 в каждую сторону. Получим квадрат со стороной 5. Плотнейшая упаковка кругов диаметра 1 в этот квадрат содержит 25 таких кругов (это ещё нужно доказать, но я не знаю как). Следовательно, если точек будет 26, то найдутся 2 точки с расстоянием меньше 1 и тогда можно нарисовать единичный круг, содержащий эти две точки. А уж тем более это верно для 37 точек (я так и не понял, что же автор имел в виду).

А как решить, если круг определить стандартно: Круг – это геометрическое место точек плоскости, расстояние от которых до заданной точки, называемой центром круга, не превосходит заданного неотрицательного числа $R$.
Тут уже нельзя допускать, чтобы окружности кругов касались друг друга.
Что делать?

[mihaild]

melnikoff в сообщении #1563686 писал(а):

Плотнейшая упаковка кругов диаметра 1 в этот квадрат содержит 25 таких кругов

А какое отношение плотнейшая упаковка имеет к задаче?
Она говорит, что если в квадрат запихали 25 непересекающихся кругов, то 26й запихать уже не получится. А совсем не про то, что они покроют весь квадрат.

melnikoff в сообщении #1563686 писал(а):

Круг – это геометрическое место точек плоскости, расстояние от которых до заданной точки, называемой центром круга, не превосходит заданного неотрицательного числа $R$

Ну так если бы вы доказали, что можно нарисовать открытый круг, содержащий две точки, то тем более можно нарисовать и замкнутый.

[melnikoff]

mihaild, я про покрытие всего квадрата ничего не говорил. Если 26-й запихнуть не получается, то мы можем запихнуть его с пересечением по крайней мере, с одним кругом. А это значит, что между центрами пересекающихся кругов расстояние меньше 1.

[mihaild]

А, да, меня сбил переход от радиуса $1/2$ к диаметру $1$ :) Да, тогда всё работает. Причем вам даже не нужна плотнейшая упаковка, и то что круги в ней не пересекаются - тоже неважно.

[waxtep]

melnikoff в сообщении #1563686 писал(а):

Плотнейшая упаковка кругов диаметра 1 в этот квадрат содержит 25 таких кругов (это ещё нужно доказать, но я не знаю как).

Можно более грубо: если ни одна пара кругов не пересекается, то их суммарная площадь не должна превышать площади квадрата $5\times5$, т.е. больше $\lfloor100/\pi\rfloor=31$ кругов точно не впихнуть

[slavav]

Числа в вашей задаче наводят на такое решение. Квадрат $4 \times 4 $ разобьём на 36 равных квадратов. Квадрат диагонали квадрата $\left(\frac{4}{6}\right)^2 + \left(\frac{4}{6}\right)^2 = \frac89$. Диагональ не превосходит единицы. Поместим 37 точек в большой квадрат. По принципу Дирихле две из них окажутся в одном маленьком квадрате. Покроем маленький квадрат окружностью единичного диаметра. Задача решена.

Вы правы про плотнейшую упаковку 25 шаров в квадрате: http://hydra.nat.uni-magdeburg.de/packing/csq/d3.html. Уже для 49 шаров плотнейшая упаковка не квадратная: http://hydra.nat.uni-magdeburg.de/packing/csq/d5.html

[waxtep]

slavav в сообщении #1563751 писал(а):

Уже для 49 шаров плотнейшая упаковка не квадратная: http://hydra.nat.uni-magdeburg.de/packing/csq/d5.html

Какая красота! Видимо для всех последующих квадратов $64,81,100,\ldots$ наиболее плотная упаковка тоже не будет квадратно-гнездовой?

[Aritaborian]

waxtep, это можно посмотреть там же, ссылки наверху и внизу страниц. Видно, что шестиугольная симметрия окончательно берёт верх над квадратной формой контейнера.

[waxtep]

Aritaborian в сообщении #1563788 писал(а):

можно посмотреть там же, ссылки наверху и внизу страниц.

Да-да, я листаю и медитирую, совершенно забросив работу

[svv]

Да, интересный сайт, спасибо slavav.
Оказывается, лишь для $N\leqslant 30$ (и для немногих бОльших $N$) доказано, что плотнейшие известные упаковки являются плотнейшими возможными. Во всём мире есть несколько энтузиастов, которые постоянно пытаются улучшить те или иные упаковки, и иногда им это удаётся:

Цитата:

Tiny improvement for N=84 by Milos Tatarevic. He wrote me that this was a very hard case. He examined over 150000 configurations, with over 1000 configurations with side length difference in range 10^-10 to 10^-15. So searching for an improvement took about 3 days.

или:

Цитата:

Astonishing improvements for such small values of N = 67, 75, 86, 91, 92 and 93 by David W. Cantrell.