Задача 105064

Темы:    [ Перестановки и подстановки (прочее) ] [ Разбиения на пары и группы; биекции ] [ Полуинварианты ] [ Индукция (прочее) ]

Сложность: 5+ Классы: 9,10,11

Условие

Авторы: Френкин Б.Р., Дерягин Д.В.

Для чисел 1, ..., 1999, расставленных по окружности, вычисляется сумма произведений всех наборов из 10 чисел, идущих подряд.
Найдите расстановку чисел, при которой полученная сумма наибольшая.

Решение

  Лемма. Пусть по окружности расставлены 1999 различных положительных чисел  a₁, a₂, ..., a₁₉₉₉  и пусть  a₁ > a₁₉₉₈.  Рассмотрим следующую операцию: числа a_i и a_1999–i  (i = 1, 2, ..., 999)  меняем местами, если  a_i < a_1999–i,  и не меняем в противном случае. Если хотя бы одна пара чисел поменялась местами, то сумма произведений десяток чисел, идущих подряд, увеличилась.
  Доказательство. Рассмотрим симметричные группы по 10 чисел  a_i, ..., a_i+9  и  a_1999–i, ..., a_1990–i.  Пусть z – произведение чисел, содержащихся одновременно и в первой, и во второй группе (произведение нулевого числа сомножителей считается равным единице);
x и x' – произведения чисел, содержащихся соответственно только в первой и только во второй группе, оставшихся на своем месте после проведения операции; y и y' – произведения чисел, содержащихся соответственно только в первой и только во второй группе, поменявшихся местами в результате операции. Тогда сумма произведений чисел в рассматриваемых двух группах до операции равна  s₁ = zxy + zx'y',  а после операции  s₂ = zxy' + zx'y.  Имеем:  s₁ – s₂ = z(x – x')(y – y').  Нетрудно видеть, что эта разность неположительна. Кроме того, если в результате операции не все числа остались на своих местах, то хотя бы для одной пары симметричных групп из 10 чисел эта разность строго отрицательна, что и доказывает лемму.

  Считаем числа 1, 2, ..., 1999 расставленными так, что дуги между соседними числами равны. Пусть числа расставлены оптимальным образом, то есть так, что сумма произведений десяток соседних чисел максимальна. Проведём диаметр через одно из чисел. Из леммы следует, что для всех пар чисел, симметричных относительно этого диаметра, меньшие числа расположены на одной полуокружности, а большие – на другой. Но такая расстановка (с точностью до поворотов и осевых симметрий) единственна (см. задачу 79433).

Ответ

См. рисунок.

         

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

олимпиада
Название	Московская математическая олимпиада
год
Номер	62
Год	1999
вариант
Класс	10
задача
Номер	6