Задача 031 — Задачи на Графы

В чемпионате по волейболу участвовало $n>2$ команд, каждые две из которых сыграли друг с другом ровно один раз. Оказалось, что для каждых двух команд есть ровно $t$ команд, у которых они обе выиграли. Докажите, что $n=4 t+3$ .

Подсказка

Решение

Возьмем любую команду $A$ . Пусть она выиграла у $k$ команд. Тогда каждая из этих $k$ команд выиграла ровно у $t$ из этих $k$ команд — иначе нарушится условие задачи относительно нее и команды $A$ . Общее число матчей в микротурнире между данными $k$ командами равно $k(k-1) / 2$ с одной стороны и общему числу побед, равному $t k$ — с другой, откуда $k=2 t+1$ . Осталось заметить, что в всем турнире было сыграно $n(n-1) / 2$ матчей и одержано $n(2 t+1)$ побед. Значит, $n(n-1) / 2=n(2 t+1)$ , откуда $n=4 t+3$ .