Олимпиадная задача: игра Чичикова и Ноздрёва с орехами – класс 8–9, теория чисел
Чичиков играет с Ноздрёвым. Сначала Ноздрёв раскладывает 222 ореха по двум коробочкам. Посмотрев на раскладку, Чичиков называет любое целое число N от 1 до 222. Далее Ноздрёв должен переложить, если надо, один или несколько орехов в пустую третью коробочку и предъявить Чичикову одну или две коробочки, где в сумме ровно N орехов. В результате Чичиков получит столько мертвых душ, сколько орехов переложил Ноздрёв. Какое наибольшее число душ может гарантировать себе Чичиков, как бы ни играл Ноздрёв.
Показать ответ
37 душ.
Разобрать решение
Оценка сверху. Положив в коробочки 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 штук.
Обсуждение
0Комментариев пока нет.