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

[e2e4]

Эээ... погодите, дайте позавтракать . На самом деле поэкспериментирую еще, чтобы упаковка была более плотной. Если получится что-то интересное - выложу.

[THC]

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

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

Очень интересно получилось:
Точки удовлетворяют условию задачи должны образовать некоторую фигуру. Эта фигура меньше по площади, чем площадь круга диаметра 21. Так что количество точек не должно быть >64. Но фигура не обязательно должна находиться внутри круга диаметра 21, зато обязательно должна находиться внутри квадрата 21x21.

[vvvv]

e2e4, что-то Вы долго завтракаете
А почему бы Вам не написать алгоритм о шарах так, как это происходит в реальности.
Кладем шары произвольно, пока они не касаются друг друга и позволяет отведенная область (граница).
Затем, гогда свободного места уже нет (так чтобы не касаться друг друга и выходить за границу ), кладем шар сверху на уже лежащие шары.
Под действием силы тяжести, сверху лежащий шар, начинает двигать соседей - те своих соседей. И так до тех пор, пока сверху лежащий шар, не коснется стола (тогда он на своих соседей уже не действует). Ну, и.т. ставим шары до тех, пока позволяет граница.
(Последний шар должен оказаться сверху на других т.к. ему не хватило места в отведенной области)

[e2e4]

vvvv, да что-то замотался я на выходных. Завтра на работу приду, подумаю .
У меня ведь почти то же самое и происходит. Надо наверное просто отключить взаимодействие, когда границы шаров не соприкасаются. Вообще-то, модель задумывалась просто поигратьсяпару часов, вряд ли она способна доказать какой-то результат, просто понравилась идея с бильярдными шарами .

[EtCetera]

Я бы хотел вернуться к мозаикам из правильных треугольников (чтобы закрыть этот вопрос раз и навсегда). Хотя интуитивно ясно, что если и существует какая-нибудь конфигурация из 50-ти точек, удовлетворяющая условию задачи, она практически наверняка будет нерегулярной, мне хотелось узнать, какой максимальный результат могут выдать мозаики.
Для начала оговорюсь, что буду считать минимальное расстояние между точками равным 1, а максимальное, соответственно, 7 (что никак не противоречит смыслу задачи, но позволяет уйти от бессмысленных троек).
Итак, если все точки, составляющие конфигурацию, лежат в вершинах правильных треугольников, уложенных в мозаику, то можно легко посчитать расстояние между двумя точками, проведя через эти точки две пересекающиеся прямые (т.е. одна прямая проходит через одну точку, а другая - через другую), параллельные сторонам треугольников и найдя расстояния от точек до точки пересечения прямых (на треугольных мозаиках это очень легко сделать). Тогда расстояние между точками будет выражаться через 2 последние величины по теореме косинусов следующим образом:
$r_{a,b}^2=a^2+b^2-2ab\cos\frac{2\pi}{3}=a^2+ab+b^2$
Посчитаем максимальные квадраты расстояний для всех $a$, не больших 4 (напомню, что квадрат расстояния между двумя точками не должен превышать $7^2=49$):
$r_{0,7}^2=49$ (очевидно)
$r_{1,6}^2=43$
$r_{2,5}^2=39$ (сильный недолет!)
$r_{3,5}^2=49$ (удивительное совпадение!)
$r_{4,4}^2=48$ (тоже очень близко)
Что здесь сразу бросается в глаза? $r_{3,5}^2$ чудесным образом оказалось равно 49, а $r_{4,4}^2$ очень хорошо приблизилось к этому расстоянию. При построении конфигураций нужно стараться, чтобы между граничными точками (на разных сторонах конфигураций) были именно такие расстояния. Также ощущается заметный "провал" в третьей строке. Дело в том, что $r_{2,6}^2=52$ - лишь ненамного больше, чем 49.
Руководствуясь этими нехитрыми соображениями, я сходу построил 2 регулярные конфигурации (больше почему-то не получилось) из 49 точек:
1. За основу первой конфигурации был взят правильный шестиугольник со стороной 3 (он состоит из 37 точек). К нему "прицеплены" 6 ушек из двух точек. Итого $37+6\cdot 2=49$.
http://docs.google.com/Doc?docid=0AZA4K ... dzRq&hl=en
2. За основу второй был взят правильный треугольник со стороной 7 (28 точек). К каждой из его сторон прикреплено "ушко" в виде трапеции с основаниями 2 и 3 (7 точек). Итого $28+3\cdot 7=49$.
http://docs.google.com/Doc?docid=0AZA4KhnEK7o_ZGc0dGJza3hfNWdtMjUzbjN6&hl=en
Обе этих конфигурации больше напоминают треугольник Рело, чем круг. Хотя построить конфигурацию из 50 точек таким образом по-видимому не удастся (и тому виной, в первую очередь, "неудачное" расстояние $r_{2,5}^2$), скорее всего существуют еще конфигурации из 49 точек, построенных на аналогичных принципах. К сожалению, вряд ли эти конфигурации можно взять за основу при построении нерегулярных конфигураций из 50-ти точек (подобных той, которую удалось получить venco).

[THC]

Очень интересно!
Только обе регулярные конфигурации в круг диаметра 21 (или 7 по новой системе отчёта) не влезут.
Наши программисты vvvv и e2e4! Поправьте пожалуйста ваши программы (замените круг на квадрат). Может быть и конфигурацию из 50 точек можно и найти

[vvvv]

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

Очень интересно!
Только обе регулярные конфигурации в круг диаметра 21 (или 7 по новой системе отчёта) не влезут.
Наши программисты vvvv и e2e4! Поправьте пожалуйста ваши программы (замените круг на квадрат). Может быть и конфигурацию из 50 точек можно и найти

EtCetera писал
Итак, если все точки, составляющие конфигурацию, лежат в вершинах правильных треугольников, уложенных в мозаику, то можно легко посчитать расстояние между двумя точками, проведя через эти точки две пересекающиеся прямые (т.е. одна прямая проходит через одну точку, а другая - через другую), параллельные сторонам треугольников и найдя расстояния от точек до точки пересечения прямых (на треугольных мозаиках это очень легко сделать). Тогда расстояние между точками будет выражаться через 2 последние величины по теореме косинусов следующим образом:
Я решительно ничего не понял

[EtCetera]

vvvv

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

Я решительно ничего не понял

Прошу прощения, действительно выразился несколько неудачно (туманно). Просто без рисунка объяснять не слишком удобно. Попробую еще раз.
Треугольная мозаика образуется из трех семейств прямых (прямые в каждом из семейств параллельны друг другу; прямые из двух различных семейств пересекаются под углом $\frac{\pi}{3}$). Точки конфигураций совпадают с точками пересечения прямых. Чтобы быстро посчитать расстояние между двумя такими точками $A_1$ и $A_2$, в данном случае проще воспользоваться не теоремой Пифагора, а теоремой косинусов. Для этого мы берем две прямые из различных семейств, одна из которых ($a_1$) проходит через первую точку, а другая ($a_2$) - через вторую, и находим точку их пересечения $B$. Из возможных вариантов пар прямых выбираем такой, что $\angle A_1 B A_2=\frac{2\pi}{3}$. Тогда квадрат расстояния $A_1A_2$ (он же $r_{a,b}^2$, где $a=A_1 B$, $b=A_2 B$) равен (по теореме косинусов) ${A_1 A_2}^2={A_1 B}^2 + {A_1 B}\cdot {A_2 B} + {A_2 B}^2=a^2+ab+b^2$.
На самом деле все это просто облегчает построение правильных конфигураций, позволяя быстро определять расстояние между двумя точками и предлагая наиболее "хорошие" (то есть близкие к 7) расстояния.

-- Пн авг 03, 2009 09:35:33 --

THC

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

Наши программисты vvvv и e2e4! Поправьте пожалуйста ваши программы (замените круг на квадрат). Может быть и конфигурацию из 50 точек можно и найти

Ну, квадрат это все-таки чересчур... Достаточно ограничиться фигурами постоянной ширины (типа треугольника Рело). Проблема в том, что площадь этих фигур меньше площади круга, поэтому если 50-ти точечная конфигурация найдется (?) именно в одной из них, это будет небольшим чудом.