ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 66312
Темы:    [ Системы точек и отрезков (прочее) ]
[ Перестройки ]
[ Суммы числовых последовательностей и ряды разностей ]
Сложность: 4
Классы: 9,10
В корзину
Прислать комментарий

Условие

На каждой из двух параллельных прямых a и b отметили по 50 точек.
Каково наибольшее возможное количество остроугольных треугольников с вершинами в этих точках?


Решение

  Очевидно, максимум достигается, когда точки на обеих прямых расположены достаточно близко, так, что каждый отрезок с отмеченными концами на одной из прямых из любой точки другой прямой виден под острым углом. Покрасим точки одной из прямых в синий цвет, а проекции на эту прямую точек второй прямой – в красный. Теперь задачу можно переформулировать следующим образом.
  На прямой отмечены 50 синих и 50 красных точек. Найти максимально возможное число троек точек, в которых средняя одного цвета, а крайние другого. Пусть A1, ..., A50, B1, ..., B50 – красные и синие точки, упорядоченные слева направо. Рассмотрим пару соседних точек Ai и Bj. Если Ai лежит левее Bj, то эти точки образуют хорошую тройку с точками B1, ..., Bj–1 и Ai+1, ..., A50, то есть  49 + (j – i)  хороших троек. При  i > j  мы можем, поменяв Ai и Bj местами, увеличить число таких троек, а остальные хорошие тройки при этом останутся хорошими. Поэтому оптимальным будет расположение точек, при котором каждая точка Ai лежит правее Bi–1, но левее Bi+1 (порядок точек Ai и Bi может быть произвольным). В частности, оптимальное расположение получится при чередовании цветов точек.
  При этом число хороших троек с красной точкой в середине равно
1·49 + 2·48 + … + 49·1 = 50(1 + 2 + … + 49) + 1² + 2² + ... + 49² = ½ 502·49 – ⅙ 49·50·99 = ⅙ 49·50·51 = 20825.  Столько же хороших троек с синей точкой в середине.


Ответ

41650.

Источники и прецеденты использования

олимпиада
Название Олимпиада по геометрии имени И.Ф. Шарыгина
год
Год 2017
класс
Класс 9
задача
Номер 9.7

© 2004-... МЦНМО (о копирайте)
Пишите нам

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .