ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам | Поиск |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 116828
Темы:    [ Теория игр (прочее) ]
[ Деление с остатком ]
Сложность: 4-
Классы: 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 душ.

Замечания

1. 5 баллов.

2. Ср. с задачей 116835.

Источники и прецеденты использования

олимпиада
Название Турнир городов
Турнир
Дата 2012/13
Номер 34
вариант
Вариант осенний тур, сложный вариант, 8-9 класс
Задача
Номер 2

© 2004-... МЦНМО (о копирайте)
     
Пишите нам
Rambler's Top100

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .