Олимпиадная задача: максимизация суммы произведений для 1999 чисел по кругу (классическая комбинаторика, 9–11 класс)

  Лемма. Пусть по окружности расставлены 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 расставленными так, что дуги между соседними числами равны. Пусть числа расставлены оптимальным образом, то есть так, что сумма произведений десяток соседних чисел максимальна. Проведём диаметр через одно из чисел. Из леммы следует, что для всех пар чисел, симметричных относительно этого диаметра, меньшие числа расположены на одной полуокружности, а большие – на другой. Но такая расстановка (с точностью до поворотов и осевых симметрий) единственна (см. задачу 179433).

См. рисунок.