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

$n$ депутаттан тұратын бір компанияда әр депутат басқа жеті депутатты құрметтейді. Сонымен қатар, бірін-бірі өзара құрметтейтін екі депутат жоқ. Осындай жағдай $n$-нің қандай ең кіші мәнінде мүмкін бола алады?

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

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

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

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

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

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

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

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