Областная олимпиада по математике, 2026 год, 9 класс

Комиссия по составлению задач состоит из нескольких авторов. Известно, что среди любых двух авторов только один доверяет другому. Каждый день каждый автор придумывает одну новую задачу и оправляет ее всем, кому доверяет, вместе со всеми задачами, полученными до этого дня (задачи, которые получил сегодня, не отправляет). Докажите, что если в третий день некий автор не получит обратно свою задачу, отправленную первый день, то существует задача, которая доходит не до всех авторов.

Комментарий/решение

​Предположим, что каждая задача доходит до всех авторов. Тогда между любыми двумя авторами есть цепочка передач, и каждый автор обязан быть частью какого-то замкнутого круга.

​Рассмотрим автора X, который не получил свою задачу на 3-й день. Раз его задача доходит до всех, она когда-нибудь к нему вернется. Пусть X->A-> B->...-> Z -> X — самый короткий путь возврата.

​Длина этого пути не может быть больше 3. Почему? Если бы в пути было 4 автора (X ->A ->B-> C->X), то из-за условия задачи (из двух доверяет только один):

​Если B доверяет X, то есть путь короче: X -> A -> B -> X (длина 3).

​Если X доверяет B, то есть путь короче: X -> B -> C -> X (длина 3).

​Значит, кратчайший путь возврата для любого автора всегда состоит ровно из 3 человек.

​Следовательно, задача X обязана вернуться к нему именно на 3-й день.

​Противоречие: По условию автор X на 3-й день задачу не получил.

Рассмотрим автора A который не получил свою задачу на третий день.Очевидно,что остальных авторов можно разбить на множества X и Y,что А отдает свои задачи X и получает задачи из Y. Предположим что кто-то из X отдает задачу кому то из Y.Очевидно,что существует некий цикл А->X-->Y->A,а это противоречит выбору автора А,так как иначе он получит свою задачу на 3-й день.

1)Допустим,что X пуст:Тогда А никому не отдаст свою задачу и задача решена.

2)Y пуст:Тогда А не получит задачи из X и задача решена.

3)X,Y непустые:Никто из Y не получит задачу,придуманной А или X и задача решена.