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