Турниры в терминах графов и не только (считаем игры и очки)

Переведём задачу на язык графов следующим образом. Вершины — шахматисты. Если игроки и сыграли вничью, не будем проводить между ними ребро, если выиграл проведём ребро со стрелочкой к в противном случае — со стрелочкой к Нам нужно найти в полученном ориентированном графе хотя бы один циклический треугольник.

Всего в графе есть потенциальных циклических треугольников.

Что может сделать треугольник не циклическим? Либо в нём нет какого-то ребра, либо в нём две стрелки идут в одну вершину. Каждое отсутствующее ребро портит треугольников. Все такие рёбра портят не более треугольников (потому что их ). По условию в каждую вершину входит стрелочки, то есть каждая вершина портит треугольников, а значит, всего таким образом испорчено не более треугольников. К сожалению, Однако по условию из каждой вершины выходит два отсутствующих ребра. То есть если игрок сыграл с и вничью, то рёбра и портят треугольник значит, мы его посчитали дважды.

Таким образом, всего испорчено не более треугольников. Следовательно, хотя бы один будет циклическим.