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

[Somewhere far beyond]

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

У меня 50 довольно легко уместились, может и 51 влезут.

50?
Интересно, а картинку можно?

[vvvv]

Исправился.Получилось -45.
И еще, число точек-периодическая функция - по оси X -3, по оси Y- 3*3^1/2, так что несложно найти максимум, но по-видимому 45-
это максимум.Как это venco уместил 50

[venco]

Просчитался - 49 получилось.

[Somewhere far beyond]

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

Просчитался - 49 получилось.

49?
Интересно, а картинку можно?

[venco]

Somewhere far beyond в сообщении #231875 писал(а):

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

Просчитался - 49 получилось.

49?
Интересно, а картинку можно?

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

[vvvv]

Я вот поэксперементировал - центр окружности перемещал в области равностороннего треугольника со стороной 3, так вот результат
толко ухудшается - получается 43 точки, 44 точки.Короче, больше 45- никак.Да это и по картине видно - никак 4 точки в окружность не
втиснуть, чтобы получилось 49.
venco, результат в студию!

[ewert]

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

Принцип такой: расставляем 21 точку по окружности диаметра 21.Следующим слоем ещё 16 точек, потом 9, и в центре ещё 3.

Я в лоб вижу только 47: 21+15+9+2.

[vvvv]

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

Somewhere far beyond в сообщении #231875 писал(а):

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

Просчитался - 49 получилось.

49?
Интересно, а картинку можно?

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

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

-- Чт июл 30, 2009 00:42:21 --

ewert в сообщении #231889 писал(а):

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

Принцип такой: расставляем 21 точку по окружности диаметра 21.Следующим слоем ещё 16 точек, потом 9, и в центре ещё 3.

Я в лоб вижу только 47: 21+15+9+2.

Дайте, пожалуйста, координаты центра окружности, чтобы можно было проверить (ваши 47)

[venco]

Видно?

[ewert]

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

Дайте, пожалуйста, координаты центра окружности, чтобы можно было проверить (ваши 47)

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

[Профессор Снэйп]

EtCetera в сообщении #230981 писал(а):

Т.е., грубо говоря, можно переформулировать задачу (в смысле, "Можно ли ещё улучшить результат?") так: на пол, выложенный правильной мозаикой из равносторонних треугольников со стороной 3, бросают обруч диаметром 21. Каково максимальное число вершин треугольников может оказаться в области внутри обруча?

Народ, объясните, пожалуйста, откуда взялась такая переформулировка. Я что-то не догоняю, откуда взялась "правильная мозаика"? Ведь в условии задачи всего лишь сказано

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

наибольшее из расстояний между ними не больше 21, а наименьшее - не меньше 3.

-- Чт июл 30, 2009 02:56:19 --

ewert в сообщении #231892 писал(а):

точки расположены не в узлах правильной решётки.

Вот-вот, и я о том же!

[ewert]

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

Народ, объясните, пожалуйста, откуда взялась такая переформулировка. Я что-то не догоняю, откуда взялась "правильная мозаика"?

Просто эвристика. Треугольная упаковка -- наиболее плотная. Конечно, с учётом ограничения она заведомо (ну или почти заведомо) неоптимальна, но для оценок -- сойдёт.

[Профессор Снэйп]

То есть это не строго?

[vvvv]

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

Видно?

Видно-то, видно, но только вопрос: на каком диаметре Вы располагаете второй слой точек? Если на 15, то 16 точек там не разместятся

[ewert]

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

То есть это не строго?

Что значит "нестрого"? То, что предлагал я -- было лишь тривиальными оценками.

-- Чт июл 30, 2009 01:13:41 --

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

на каком диаметре Вы располагаете второй слой точек? Если на 15, то 16 точек там не разместятся

Не разместились бы; но они и не "на диаметре", а просто поставлены методом какого-то научного тыка.