Задача
На окружности расставлено несколько положительных чисел, каждое из которых не больше 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.
Ответ
Ответ задачи отсутствует
Чтобы оставлять комментарии, войдите или зарегистрируйтесь