Задача
Как надо расположить числа 1, 2, ..., 1962 в последовательности a1, a2, ..., a1962, чтобы сумма |a1 – a2| + |a2 – a3| + ... + |a1961 – a1962| + |a1962 – a1| была наибольшей?
Решение
Отметим на числовой прямой точки 1, 2, ..., 1962. Каждому расположению чисел в последовательности ai можно поставить в соответствие замкнутую ломаную с вершинами ai, обходящую их по разу. И наоборот, каждой такой ломаной соответствует последовательность ai. В задаче требуется найти ломаную с максимальной длиной. Длина каждой такой ломаной равна сумме длин отрезков между соседними точками с учётом кратности его покрытия звеньями.
Отрезок [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.
Чтобы оставлять комментарии, войдите или зарегистрируйтесь