Детская олимпиадная задача

[vvvv]

venco в сообщении #231942 писал(а):

Профессор Снэйп в сообщении #231938 писал(а):

vvvv в сообщении #231922 писал(а):

...если сравнить длины отрезков, изображенных красным, визуально, то видно, что меньший отрезок меньше 3-х.

Чисто визуально меньший из двух красных отрезков --- это, в точности, радиус одной из окружностей, так что его длина равна трём

Именно так!

-- Ср июл 29, 2009 20:11:21 --

vvvv в сообщении #231940 писал(а):

21 отрезок длиной 3 на окружности диаметром 21 отложить невозможно т.к. не выполняется условие 21*Sin(pi/21)<=3.

Не-а, возможно. Как раз потому что >3.
vvvv, посчитайте ещё раз, только теперь правильно.

Да, я промахнулся, поздно (рано) уже - голова не соображает, пора ложиться спать.
Ну, да.Вы ( программа) сначала откладывала хорды длиной 3 18 шт., а 19-21 оказались больше 3-х. т.к. 21*Sin(pi/21)=3.13

[vvvv]

Итак, разместилось 49 точек (может быть 50 ), тогда возникает вопрос: почему авторы задачи более чем в четыре с половиной раза
увеличили оценку.Ведь не только 225 точек нельзя разместить, но по-видимому и 50

[RIP]

vvvv в сообщении #231994 писал(а):

тогда возникает вопрос: почему авторы задачи более чем в четыре с половиной раза увеличили оценку.

Видимо, такое у них было решение. Интересно, какое, ведь самое тупое и безыдейное решение (если окружить каждую точку кругом радиуса 1.5, то круги не будут перекрываться и с большим комфортом разместятся в квадрате со стороной 24) даёт оценку $\lfloor24^2/(\pi\cdot1.5^2)\rfloor=81$.

-- Чт 30.7.2009 14:46:09 --

Хмм... Если размещать точки не в квадрате, а в круге радиуса 21, то получается ровно 225...

[vvvv]

RIP в сообщении #232009 писал(а):

vvvv в сообщении #231994 писал(а):

тогда возникает вопрос: почему авторы задачи более чем в четыре с половиной раза увеличили оценку.

Видимо, такое у них было решение. Интересно, какое, ведь самое тупое и безыдейное решение (если окружить каждую точку кругом радиуса 1.5, то круги не будут перекрываться и с большим комфортом разместятся в квадрате со стороной 24) даёт оценку $\lfloor24^2/(\pi\cdot1.5^2)\rfloor=81$.

-- Чт 30.7.2009 14:46:09 --

Хмм... Если размещать точки не в квадрате, а в круге радиуса 21, то получается ровно 225...

Да, странная оценка.Я о другом, оказывается, найденным venco способом, можно наиболее компактно и выгодно упаковывать
связки труб.Правда внешний "габаритный" диаметр будет 24.
venco, Вы можете нарисовать картинку, как будут выглядеть эти трубы (в сечении)

[Somewhere far beyond]

venco в сообщении #231883 писал(а):

На картинке трудно будет разглядеть.
Принцип такой: расставляем 21 точку по окружности диаметра 21.
Следующим слоем ещё 16 точек, потом 9, и в центре ещё 3.
Всего - 49, и есть несколько мест, где почти влезает ещё одна точка. Может и влезть, если подвигать.

Да, вы правы, действительно 49 точек удовлетворяют условию задачи.
Попробовал "впихивать" точки, и да образуется пустая область в которую возможно без 5-10% вписать 50-ю точку.
Интересен вопрос: возможно ли решение при 50? если да, то как его найти?

Данную задачу можно (приближенно*) переформулировать следующим образом:
Разместить в круге радиусом $8N$, $50$ непересекающихся кругов радиусом $N$.
(*) - так как в виду иррациональности числа $\pi$, в оптимальном случае внешняя граница не окружность.

Для решения необходим метод построения поля точек касания кругов.
Метод "научного тыка" - хороший метод, но не всегда дает точный результат.

Предлагается следующий метод:

Вспомнился случай, что как легко, накидав в бильярдный треугольник 5 шаров, поместить 6-й и шары строго "ложатся" по форме.

Эксперимент:
Инструменты: 50 бильярдных шаров, жесткий цилиндр радиусом в 8 раз больше радиуса бильярдного шара, ровный стол.
Помещаем 49 шаров в цилиндр, так что бы каждый касался стола. После пробуем вставить 50-й шар в разные "пустые места" так, что бы все касались стола.
При получении результата, составить поле касаний и проанализировать математически, исключая физическую погрешность.

При отсутствии инструментов эксперимента, смоделировать на компьютере.

[ИСН]

To add more confusion: существование большого круга, в который влезают малые, из условий задачи не следует. Может, они это в треугольник Рело влезают, кто их знает...

[vvvv]

На компьютере смоделировать такой эксперемент, по-моему, непросто.

[e2e4]

Вот набросал программку. Большая окражность в масштабе диамтером 21, малые - радиусом 3. После размещение 35 точек моделирование замирает каждый раз, когда достигнуты условия задачи. Больше 42 разместить не удалось пока, надо экспериментировать с константами модели или что-то менять. Может быть кому-то будет интересно.

-- Пт июл 31, 2009 20:59:08 --

ИСН писал(а):

To add more confusion: существование большого круга, в который влезают малые, из условий задачи не следует. Может, они это в треугольник Рело влезают, кто их знает...

По-моему, следует... Расстояние между любыми точками не должно быть больше 21. Ну, конечно, точки можно теоретически разместить и более компактно, но они заведомо будут в пределах окружности диаметром 21.

[RIP]

e2e4 в сообщении #232308 писал(а):

Расстояние между любыми точками не должно быть больше 21. Ну, конечно, точки можно теоретически разместить и более компактно, но они заведомо будут в пределах окружности диаметром 21.

Не факт. Попробуйте, например, правильный треугольник со стороной 21 запихать в круг такого диаметра.

[vvvv]

e2e4, Вашу программу опробовал- работает.Если добавлять точки далее, то замерание прекращается.
Почему Вы сделали радиус малой окружности 3?, тогда расстояние минимальное между точками будет 6, а по условию задачи - 3 т.е.
радиус малых окружностей должен быть 1,5.
У Вас две больших концентрических окружности: меньшая диаметром 21, а большая, как я понял, - 24?

[THC]

А я доказал строго, что если точки удовлетворяют условию задачи, то они должны находиться внутри квадрата 21x21
Так что возьмите квадрат, а не окружность, при программировании

-- Сб авг 01, 2009 08:24:26 --

Кстати раньше я доказал для 169 точек, я исходил из того, что все точки должны заключаться в полосе шириной 21. А если из квадрата 21x21, то можно доказать результат 90 точек господина TOTAL.

[RIP]

THC в сообщении #232349 писал(а):

Кстати раньше я доказал для 169 точек, я исходил из того, что все точки должны заключаться в полосе шириной 21. А если из квадрата 21x21, то можно доказать результат 90 точек господина TOTAL.

Точнее, 81.
А если учесть, что среди всех фигур данного диаметра наибольшую внешнюю меру Лебегаплощадь имеет круг, то сразу получаем оценку 64.

[THC]

RIP в сообщении #232353 писал(а):

THC в сообщении #232349 писал(а):

Кстати раньше я доказал для 169 точек, я исходил из того, что все точки должны заключаться в полосе шириной 21. А если из квадрата 21x21, то можно доказать результат 90 точек господина TOTAL.

Точнее, 81.

Всё верно, RIP

[e2e4]

RIP писал(а):

Не факт. Попробуйте, например, правильный треугольник со стороной 21 запихать в круг такого диаметра.

А, точно. Ну тогда квадрат надо рассматривать.

ТНС писал(а):

e2e4, Вашу программу опробовал- работает.Если добавлять точки далее, то замерание прекращается.

Это потому, что не находится положения, удовлетворяющего условиям задачи.

ТНС писал(а):

Почему Вы сделали радиус малой окружности 3?, тогда расстояние минимальное между точками будет 6, а по условию задачи - 3 т.е.
радиус малых окружностей должен быть 1,5.

Радиус маленьких действительно 1,5, диаметр 3. Я ошибся в описании.

ТНС писал(а):

У Вас две больших концентрических окружности: меньшая диаметром 21, а большая, как я понял, - 24?

На большую окружность можно не обращать внимания, она состоит из неподвижных точечных зарядов. Точки же - подвижные заряды, вся система подчиняется закону Кулона, отсюда такое забавное поведение точек.

[vvvv]

Где же e2e4 со своей исправленной программой?