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

Проект МЦНМО
при участии
школы 57
Задача 116835
Темы:    [ Теория игр (прочее) ]
[ Деление с остатком ]
[ Принцип Дирихле (углы и длины) ]
Сложность: 4-
Классы: 10,11
В корзину
Прислать комментарий

Условие

Чичиков играет с Ноздрёвым. Сначала Ноздрёв раскладывает 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.

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

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

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

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