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

[THC]

Доказать, что нельзя отметить на плоскости 225 точек так, чтобы наибольшее из расстояний между ними не больше 21, а наименьшее - не меньше 3.
(Это задача из XIV международной олимпиады "Интеллектуальный марафон". Её решение имеется в "Кванте" 03/2006 (стр.62)).

Но я шёл другим путём и мне удалось доказать более "сильный" результат . А именно:
Нельзя отметить на плоскости 169 точек так, чтобы наибольшее из расстояний между ними не больше 21, а наименьшее - не меньше 3.

Пожалуйста,
1) Решайте эту задачку в её первоначальном виде. Просто так, ради удовольствия
2) Докажите мой результат. Если я ошибся, то отпровергните его!
3) Можно ли ещё улучшить результат?. Т.е. ещё уменьшить количество точек при сохранении заданных условий задачи?

[TOTAL]

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

3) Можно ли ещё улучшить результат?

90 точек, точнее считать неохота

[ewert]

Больше 61 уж никак не выйдет, да и это с запасом.

[EtCetera]

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

Больше 61 уж никак не выйдет, да и это с запасом.

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

[imbecile]

Напишите пожалуйста набросок решения для 61.

[THC]

Найти нижний предел количеству точек и потом это строго доказать, наверно, очень трудно...
Но оценить его с высокой (опять неизвестно, какой) точностью можно. На компьютере.
Мой примитивный алгоритм такой:
Разделим квадрат 21x21 на мельчайшие квадратики размером 0.1 или 0.001, ... (в зависимости от мощности компьютера). Растояние между любыми двумя точками в узлах легко определить по теореме Пифагора.
И поехали: Проверим все комбинаций n точек в узлах (n пробежит от 35 до 61)

[worm2]

Боюсь, никакого компьютера не хватит. Всевозможных выборок 35 квадратов из $21^2 = 441$, по моим прикидкам, больше $10^{50}$.

[THC]

Вы правы, worm2, никакого компьютера не хватит!
Лучше, конечно, применяем метод предложенный выше EtCetera.
С помощью генератора случайных чисел тысяча или миллион раз бросаем обруч на пол. Очень просто каждый раз вычислить сколько вершин треугольников оказавшихся внутри него...

[ewert]

imbecile в сообщении #231032 писал(а):

Напишите пожалуйста набросок решения для 61.

61 -- это шестиугольник, составленный из $9+(8+7+6+5)+(8+7+6+5)$ монеток диаметром $3$. В круг диаметром $24$ они точно не влезут.

Да, кстати, а шестиугольник (неправильный) $44=8+(7+6+5)+(7+6+5)$ -- точно влезет. Оценки, конечно, очень грубые.

[Somewhere far beyond]

45 - можно.
46 - не получилось (скорее всего нельзя).
47 - нельзя.

[vvvv]

Что-то, ребята, я вас не понимаю.
С помощью простенькой программки нарисовал и подсчиталь максимальновозможное число точек, удовлетворяющих
условию задачи.У меня получилось -180.А минимальное число - 2.
Вот картинка

[Утундрий]

Чтобы проникнуться важностью задачи мне недостает понимания богоизбранности констант 21 и 3...

[ewert]

Утундрий в сообщении #231857 писал(а):

Чтобы проникнуться важностью задачи мне недостает понимания богоизбранности констант 21 и 3...

Очень просто. $21=3\times7.$ Тройко, семёрко, туз...

-- Ср июл 29, 2009 23:08:38 --

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

У меня получилось -180.А минимальное число - 2.
Вот картинка

У Вас максимальное расстояние всяко не меньше 40, а надо не больше 21.

[venco]

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

45 - можно.
46 - не получилось (скорее всего нельзя).
47 - нельзя.

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

[vvvv]

Оx, проиахнулся - взял радиус 21, а нужно диаметр, сейчас исправим