Задача 66312

Темы:    [ Системы точек и отрезков (прочее) ] [ Перестройки ] [ Суммы числовых последовательностей и ряды разностей ]

Сложность: 4 Классы: 9,10

Условие

Автор: Кожевников П.А.

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

Решение

  Очевидно, максимум достигается, когда точки на обеих прямых расположены достаточно близко, так, что каждый отрезок с отмеченными концами на одной из прямых из любой точки другой прямой виден под острым углом. Покрасим точки одной из прямых в синий цвет, а проекции на эту прямую точек второй прямой – в красный. Теперь задачу можно переформулировать следующим образом.
  На прямой отмечены 50 синих и 50 красных точек. Найти максимально возможное число троек точек, в которых средняя одного цвета, а крайние другого. Пусть A₁, ..., A₅₀, B₁, ..., B₅₀ – красные и синие точки, упорядоченные слева направо. Рассмотрим пару соседних точек A_i и B_j. Если A_i лежит левее B_j, то эти точки образуют хорошую тройку с точками B₁, ..., B_j–1 и A_i+1, ..., A₅₀, то есть  49 + (j – i)  хороших троек. При  i > j  мы можем, поменяв A_i и B_j местами, увеличить число таких троек, а остальные хорошие тройки при этом останутся хорошими. Поэтому оптимальным будет расположение точек, при котором каждая точка A_i лежит правее B_i–1, но левее B_i+1 (порядок точек A_i и B_i может быть произвольным). В частности, оптимальное расположение получится при чередовании цветов точек.
  При этом число хороших троек с красной точкой в середине равно
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