Областная олимпиада по математике, 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 и задача решена.