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

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

Условие

У повара в подчинении десять поварят, некоторые из которых дружат между собой. Каждый рабочий день повар назначает одного или нескольких поварят на дежурство, а каждый из дежурных поварят уносит с работы по одному пирожному каждому своему недежурящему другу. В конце дня повар узнает количество пропавших пирожных. Сможет ли он за 45 рабочих дней понять, кто из поварят дружит между собой, а кто нет?


Решение

  Пусть повар установит такую схему дежурств: первые девять поварят сначала дежурят поодиночке, а затем дежурят все возможные пары из этих поварят. Так как из 9 поварят всего можно выбрать 36 пар, то уйдёт ровно  9 + 36 = 45  рабочих дней.
  Возьмём произвольных поварят A и B из первых девяти и посмотрим на количества пропавших пирожных в день, когда дежурил только A, в день, когда дежурил только B, и в день, когда A и B дежурили вместе. Поварята A и B не дружат между собой тогда и только тогда, когда количество пирожных, пропавших в третий день, равно сумме количеств пирожных, пропавших в первый и второй дни.
  Пусть A поварёнок из первых девяти, а C – десятый поварёнок. Из количества пропавших пирожных в день одиночного дежурства A вычтем количество его друзей среди первых девяти поварят (это количество мы уже определили). Если получится ноль, то A и C не дружат между собой, иначе – дружат.


Ответ

Сможет.

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

олимпиада
Название Московская математическая олимпиада
год
Год 2014
Номер 77
класс
Класс 11
задача
Номер 4

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

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