|
|
 |
Условие
Чичиков играет с Ноздрёвым. Сначала Ноздрёв раскладывает 1001 орех по трём коробочкам. Посмотрев на раскладку, Чичиков называет любое целое число N от 1 до 1001. Далее Ноздрёв должен переложить, если надо, один или несколько орехов в пустую четвёртую коробочку и предъявить Чичикову одну или несколько коробочек, где в сумме ровно N орехов. В результате Чичиков получит столько мертвых душ, сколько орехов переложил Ноздрёв. Какое наибольшее число душ может гарантировать себе Чичиков, как бы ни играл Ноздрёв?
Решение
Оценка сверху. Положив в коробочки 143, 286 = 2·143 и 572 = 4·143 ореха, Ноздрёв может при любом N переложить не более 71. Действительно, N можно представить в виде 143k + r, где 0 ≤ k ≤ 7, а –71 ≤ r < 71. Если r = 0, то k > 0, и число 143k можно набрать одной или несколькими коробочками, ничего не перекладывая. Если r < 0, то набрав коробочками число 143k, отложим из этих коробочек в пустую r орехов. Если r > 0, то 1001 – N = 143(7 – k) – r. Переложив r орехов, получим несколько коробочек с 1001 – N орехами. Тогда в остальных коробочках N орехов, их и предъявим.
Оценка снизу. Покажем, что для любой раскладки есть N, которое потребует переложить не менее 71 ореха. Пусть в коробочках лежат x, y и z орехов. Шесть чисел x, y, z, x + y, x + z, y + z делят большой отрезок [0, 1001] на семь меньших (возможно, некоторые из них вырождены). Среди них есть отрезок длины не менее 1001 : 7 = 143. На этом отрезке есть целое число, отстоящее от концов отрезка не менее чем на 71. Без перекладывания мы можем получать только наборы, где общее число орехов лежит на конце одного из семи малых отрезков. Чтобы изменить это число на r, надо переложить не менее r орехов.
Ответ
71 душу.
Замечания
1. 5 баллов.
2. Ср. с задачей 116828.
