Олимпиадная задача: игра Чичикова и Ноздрёва с орехами – класс 8–9, теория чисел
Задача
Чичиков играет с Ноздрёвым. Сначала Ноздрёв раскладывает 222 ореха по двум коробочкам. Посмотрев на раскладку, Чичиков называет любое целое число N от 1 до 222. Далее Ноздрёв должен переложить, если надо, один или несколько орехов в пустую третью коробочку и предъявить Чичикову одну или две коробочки, где в сумме ровно N орехов. В результате Чичиков получит столько мертвых душ, сколько орехов переложил Ноздрёв. Какое наибольшее число душ может гарантировать себе Чичиков, как бы ни играл Ноздрёв.
Решение
Оценка сверху. Положив в коробочки 74 и 148 орехов, Ноздрёв может при любом N переложить не более 37. Действительно, N можно записать в виде 74k + r, где k = 0, 1, 2, 3, а –37 ≤ r < 37. Если r = 0, то k > 0, и числа 74, 148 и 222 можно набрать одной или двумя коробочками, ничего не перекладывая. Если r < 0, то набрав число 74k одной или двумя коробочками, отложим из этих коробочек в третью r орехов. Если r > 0, 74k = 0, 74 или 148. Взяв подходящую коробочку или не взяв ни одной, добавив к ним третью коробочку, куда из не взятой переложены r орехов.
Оценка снизу. Покажем, что для любой раскладки есть N, которое потребует переложить не менее 37 орехов. Пусть в коробочках лежат p и q орехов,
q ≥ p. Если p ≥ 74, то при N = 37 придётся переложить не менее 37 орехов. Если p < 74, то q > 148. Чтобы получить N = 111 надо либо к p орехам добавить более 37 штук, либо от q орехов отнять более 37 штук.
Ответ
37 душ.
Чтобы оставлять комментарии, войдите или зарегистрируйтесь