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

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

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

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

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

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

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

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

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

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

Пусть $n$ количество депутатов. Представим их как вершины ориентированного графа, где ребро $A \to B$ означает, что депутат $A$ уважает депутата $B$.

Из условия следует, что из каждой вершины выходит ровно 7 ребер. Общее количество ребер в графе равно:

$$E = 7n$$

В компании нет взаимного уважения. Это означает, что если существует ребро $A \to B$, то ребра $B \to A$ быть не может. Таким образом, между любой парой вершин $(A, B)$ может существовать максимум одно ориентированное ребро.

Общее количество пар вершин в графе из $n$ элементов равно $\frac{n(n-1)}{2}$. Следовательно, общее количество фактически проведенных ребер $E$ не может превышать количество доступных пар:

$$E \le \frac{n(n-1)}{2}$$

Подставим $E = 7n$ в неравенство:

$$7n \le \frac{n(n-1)}{2}$$

Так как $n > 0$, сократим на $n$:

$$7 \le \frac{n-1}{2} \implies 14 \le n - 1 \implies n \ge 15$$

Пример для $n = 15$: Расположим депутатов по кругу. Пусть каждый $i$-й депутат уважает депутатов с номерами $(i+1, i+2, \dots, i+7) \pmod{15}$.

Если $A$ уважает $B$, то расстояние от $A$ до $B$ по часовой стрелке составляет $k \in \{1, \dots, 7\}$.

Для взаимного уважения расстояние от $B$ до $A$ должно быть в том же диапазоне, но оно равно $15 - k$.

Если $1 \le k \le 7$, то $8 \le 15 - k \le 14$.

Диапазоны не пересекаются, значит, взаимное уважение невозможно.

Ответ: 15