Решение задачи 502
Чичиков играет с Ноздрёвым. Сначала Ноздрёв раскладывает 1001 орех по трём коробочкам. Посмотрев на раскладку, Чичиков называет любое целое число N от 1 до 1001. Далее Ноздрёв должен переложить, если надо, один или несколько орехов в пустую четвёртую коробочку и предъявить Чичикову одну или несколько коробочек, где в сумме ровно N орехов. В результате Чичиков получит столько мертвых душ, сколько орехов переложил Ноздрёв. Какое наибольшее число душ может гарантировать себе Чичиков, как бы ни играл Ноздрёв?
Обозначим через a, b, c количества орехов в трех коробках. Ноздрев оперирует с восемью числами: 0, a, b, c, a + b, b + c, a + c, 1001 (a + b + c). Рассмотрим отрезок [0;1001] и отметим на нем восемь вышеперечисленных чисел. Отрезок в общем случае разбивается на семь частей. Пусть Чичиков назвал число N. Рассмотрим минимальное расстояние от N до одного из отмеченного числа. Это минимальное количество орехов необходимое переложить Ноздреву, чтобы предъявить коробки с суммарным числом N. Таким образом, при фиксированном расположении орехов Чичиков может получить максимум половину (с округлением вниз) длины наибольшего отрезка душ.
Как же расположить орехи, чтобы Чичиков получил как можно меньше? Надо минимизировать длину максимального отрезка. Заметим, что длина наибольшего отрезка не меньше 1001 / 7 = 143, то есть Чичиков гарантировано получает 71 душу. Ноздрев может расположить орехи так: 143, 286, 572, тогда отрезок [0;1001] разобьется на семь равных отрезков, то есть больше 71 души Чичиков не сможет получить.