При $n = 4$ всего $C(4,2) = 6$ игр. Проверим, что гамильтонов путь существует всегда. Упорядочим команды по числу побед в порядке убывания. Если у двух команд одинаковое число побед, рассмотрим результат их личной встречи. Формальное доказательство по индукции: при $n=1$ тривиально. Допустим верно для $n -1$. Из $n$ команд выберем команду с наибольшим числом побед (она выиграла хотя бы у половины). Для оставшихся $n -1$ уже есть путь $t_1$,...$,t_{n-1}$. Если добавляемая команда $v$ победила $t_1$, то путь $v, t_1$,...$,t_{n-1}$. Иначе найдём наименьшее $i$, где $t_i$ победила $v$, а значит $t_{i-1}$ проиграла $v$, и вставим $v$ между $t_{i-1}$ и $t_i$.

💡 Авторизуйтесь, чтобы получить помощь AI-тьютора с подсказками и решениями!