қазақша
русскийОбластная олимпиада по математике, 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-й день задачу не получил.
Красивая задача — это по сути про ориентированный турнир и распространение информации.
Переформулируем аккуратно.
---
Обозначения
Есть авторы, между любой парой ровно один доверяет другому.
Значит, граф доверия — турнир: для любых двух есть ровно одно направленное ребро.
Каждый день:
каждый автор придумывает новую задачу;
отправляет её всем, кому он доверяет;
и вместе с ней отправляет все задачи, полученные в прошлые дни
(но не те, что получил сегодня).
---
Что нужно доказать
Если на 3-й день некоторый автор не получил свою задачу, придуманную в 1-й день,
то существует задача, которая не дошла до всех авторов.
То есть система распространения не является «полной».
---
Ключевая идея
Если все задачи всегда доходят до всех, то информация должна быстро «замыкаться» в турнире.
Мы покажем, что из того, что задача не вернулась к за 3 дня, следует существование автора, до которого она вообще не может дойти.
---
Шаг 1. Кто мог вернуть задачу обратно?
Пусть — автор, придумавший задачу в 1-й день.
Чтобы получил её обратно к 3-му дню, должна существовать цепочка вида:
x \to a \to b \to x
где стрелка означает «доверяет» (и значит — посылает задачи).
Если такой цепочки нет, то задача физически не может вернуться.
---
Шаг 2. Что значит, что цепочки нет?
Раз не получил свою задачу к 3-му дню, значит:
> Для любых :
если и , то не верно, что .
То есть:
x\to a,\ a\to b \;\Rightarrow\; x\to b.
Иначе говоря:
> Все, до кого задача может дойти за 2 шага, тоже доверяют .
---
Шаг 3. Разобьём авторов на два множества
Обозначим:
— все авторы, которым доверяет
— все авторы, которые доверяют
(кроме самого).
Так как это турнир, все авторы разбиваются на .
---
Шаг 4. Ключевое свойство
Мы показали выше:
> Если и , то .
Значит:
❗ Из нельзя выйти по стрелкам доверия.
Все рёбра между и направлены из в .
Схематично:
B ---> A ---> (внутри A)
\ |
\------>|
Из в стрелок нет.
---
Шаг 5. Что происходит с задачей из ?
Возьмём любого автора и его задачу .
В день 1 он рассылает её тем, кому доверяет — то есть только в .
Все, кто получит её дальше, тоже могут отправить её только внутри .
Следовательно:
> Ни одна задача, появившаяся в , никогда не попадёт в .
---
Финал
Мы получили:
— непусто (туда входят все, кому доверяет ).
— непусто (иначе задача сразу бы вернулась).
Из информация никогда не попадает в .
Значит:
> Любая задача, придуманная автором из ,
не доходит до всех авторов.
Что и требовалось доказать. ✅
---
Интуиция в одной фразе
Если за 3 дня задача не может вернуться к автору, значит в графе доверия есть «запертая часть», из которой информация не выходит — а значит, существует задача, которая не доходит до всех.
---
Если хочешь, могу:
сделать краткую олимпиадную версию доказательства;
или оформить в стиль «решение для жюри».
Возможно, что при неправильном наборе формул, они будут
доредактированы модератором. При этом содержание не будет меняться.