ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам | Поиск |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 65833
Темы:    [ Разбиения на пары и группы; биекции ]
[ Принцип крайнего (прочее) ]
[ Алгебраические неравенства (прочее) ]
[ Доказательство от противного ]
Сложность: 4-
Классы: 9,10,11
В корзину
Прислать комментарий

Условие

На окружности расставлено несколько положительных чисел, каждое из которых не больше 1. Докажите, что можно разделить окружность на три дуги так, что суммы чисел на соседних дугах будут отличаться не больше чем на 1. (Если на дуге нет чисел, то сумма на ней считается равной нулю.)


Решение

Первый способ. Назовём весом дуги сумму чисел на ней (у дуги без чисел вес 0), а разбросом – разность между наибольшим и наименьшим весом. Число отличающихся весами разбиений конечно, выберем из них разбиение с наименьшим разбросом. Докажем, что это разбиение – искомое. Допустим, разность между наибольшим весом c дуги C и наименьшим весом a дуги A больше 1. Cдвинем границу между дугами так, чтобы ровно одно число r перешло с C на A. После этого мы получим новое разбиение: на дуги A', B и C' с суммами  a' = a + r,  b,  c' = c – r.  Легко проверить, что каждая из разностей  c' – a',  b – a',  c' – b  меньше  c – a,  но больше –1, то есть разброс в противоречие с выбором первого разбиения уменьшился.

Второй способ. Рассмотрим разбиение, для которого сумма квадратов весов наименьшая. Докажем, что это разбиение и является искомым. Пусть A и B – соседние дуги с весами a и  b > a.  Cдвинем границу между дугами так, чтобы ровно одно число r с B перешло на A. По выбору разбиения
a² + b² ≤ (a + r)² + (b – r)² = a² + b² + 2r(r – (b – a)),  то есть  b – a ≤ r ≤ 1.

Замечания

1. Вторым способом точно так же доказывается, что можно разделить окружность на любое наперёд заданное число дуг с соблюдением указанного условия.

2. 6 баллов.

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

олимпиада
Название Турнир городов
Турнир
Номер 27
Дата 2005/2006
вариант
Вариант осенний тур, основной вариант, 10-11 класс
задача
Номер 4

© 2004-... МЦНМО (о копирайте)
     
Пишите нам
Rambler's Top100

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .