Задача 78293

Темы:    [ Алгебраические неравенства (прочее) ] [ Наибольшая или наименьшая длина ]

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

Условие

Как надо расположить числа 1, 2, ..., 1962 в последовательности a₁, a₂, ..., a₁₉₆₂, чтобы сумма  |a₁ – a₂| + |a₂ – a₃| + ... + |a₁₉₆₁ – a₁₉₆₂| + |a₁₉₆₂ – a₁|  была наибольшей?

Решение

  Отметим на числовой прямой точки 1, 2, ..., 1962. Каждому расположению чисел в последовательности a_i можно поставить в соответствие замкнутую ломаную с вершинами a_i, обходящую их по разу. И наоборот, каждой такой ломаной соответствует последовательность a_i. В задаче требуется найти ломаную с максимальной длиной. Длина каждой такой ломаной равна сумме длин отрезков между соседними точками с учётом кратности его покрытия звеньями.
  Отрезок  [s, s + 1]  может покрываться только звеньями, один конец каждого из которых лежит в множестве  {1, ..., s},  а другой – в множестве
{s + 1, ..., 1962}.  Причём каждой вершине любого из этих множеств отвечает не более двух звеньев, а значит, покрывать отрезок  [s, s + 1]  может не более
2 min(s, 1962 – s)  звеньев.
  Осталось построить ломаную, достигающую полученного максимума. Несложно проверить, что ломаная, соответствующая последовательности
881, 881 + 1, 881 – 1, 881 + 2, 881 – 2, ..., 881 + i, 881 – i, ..., 881 + 881,  является искомой.

Ответ

Например:  881, 882, 880, 883, 879, ..., 881 + i, 881 – i, ..., 1962.

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

олимпиада
Название	Московская математическая олимпиада
год
Номер	25
Год	1962
вариант
	1
Класс	8
Тур	2
задача
Номер	2