ММО-2014. Повар и поварята

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

Автор задачи - О.Н. Косухин. Задача была предложена на Московской математической олимпиаде 2014 года одиннадцатиклассникам.

Прежде чем обсуждать решение исходной задачи, рассмотрим упрощение.

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

Тут попроще. Ведь сразу понятно, что надо два дня ставить этих поварят дежурить поодиночке, а в третий день поставить их дежурить вместе. После этого считаем сумму пропавших в первые два дня пирожных и сравниваем с тем, сколько пропало в последний день. Если они не являются друзьями, то пропало поровну. Если друзья, то в третий день им не было смысла таскать пирожные друг другу, и число пропавших пирожных в этот день меньше.

Теперь разберём решение исходной задачи. Выберем девять (не десять!) поварят, чтобы они дежурили сначала поодиночке, а потом те же девять дежурили по парам. Таким образом, пройдёт 9+9*8/2=45 дней.
Поймём, что мы теперь можем узнать всё про дружбы поварят.
Для каждой пары мы уже можем сказать, дружат они или нет. Ведь среди 45 дней найдутся три, нужные нам для решения упрощённой задачи.

Т.е. мы понимаем, кто с кем дружит из девяти работавших. Как понять про десятого? Да просто вычесть число пирожных, унесённых k-м поварёнком из числа его друзей среди выделенных девяти. Если будет 0, то он с десятым не дружит. Если 1, то дружит.