Городская Жаутыковская олимпиада по математике, 8 класс, 2026 год

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

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

Рассмотрим граф, где вершины—это депутаты

Проведём ребро со стрелкой от депутата А к депутату Б, если А уважает Б.

Всего рёбер 7n

Заметим, что одного депутата должны уважать семеро других. Если это не так, то каждого уважает не более шестеро других и рёбер =<6n

Значит есть депутат, которого уважают семеро других, и он сам уважает других семерых

Значит депутатов не менее 15

Пример: рассадим всех 15 за круглым столом, таким образом, чтоб депутаты уважали семерых следующих за ними по часовой стрелке