Задача 115407

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

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

Условие

Автор: Богданов И.И.

По кругу стоят 2009 целых неотрицательных чисел, не превышающих  100 . Разрешается прибавить по 1 к двум соседним числам, причем с любыми двумя соседними числами эту операцию можно проделать не более k  раз. При каком наименьшем k все числа гарантированно можно сделать равными?

Решение

Обозначим числа на окружности через  a₁,..,a2009 , и положим a_n+2009=a_n=a_n-2009 . Пусть N=100400 .
1. Положим a₂=a₄=..=a2008=100 и a₁=a₃=..=a2009=0 . Пусть мы сумели сделать все числа равными при каком-то значении  k . Рассмотрим сумму S=(a₂-a₃)+(a₄-a₅)+..+(a2008-a2009) . Эта сумма увеличивается на  1 при прибавлении единицы к паре  (a₁,a₂) , уменьшается на  1 при прибавлении к паре  (a2009,a₁) и не изменяется при всех остальных операциях. Поскольку исходное значение  S равно  S₀=100· 1004=N , а конечное должно быть нулем, то пара  (a2009,a₁) увеличивалась хотя бы N раз. Это значит, что k N .
2. Осталось показать, что при k=N требуемое всегда возможно. Рассмотрим произвольный набор чисел a_i . Увеличим каждую пару (a_i,a_i+1) ровно  s_i=a_i+2+a_i+4+..+a_i+2008 раз. Тогда число  a_i превратится в

a_i+s_i-1+s_i =a_i+(a_i+1+a_i+3+..+a_i+2007)+


+ (a_i+2+a_i+4+..+a_i+2008) =a₁+..+a2009,
то есть все числа станут равными. С другой стороны, s_i 1004· 100=N , что и требовалось.

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

олимпиада
Название	Всероссийская олимпиада по математике
год
Год	2008-2009
Этап
Вариант	5
Класс
Класс	10
задача
Номер	06.4.10.4