|
|
 |
Условие
В однокруговом хоккейном турнире принимало участие 2016 команд. По регламенту турнира за победу даётся 3 очка, за поражение 0 очков, а в случае ничьей назначается дополнительное время, победитель которого получает 2 очка, а проигравший – 1 очко. По окончании турнира Остапу Бендеру сообщили количество очков, набранных каждой командой, на основании чего он сделал вывод, что не менее N матчей закончились дополнительным временем. Найдите наибольшее возможное значение N.
Решение
Рассмотрим полный ориентированный граф, вершинами которого будут команды – участницы турнира, а ребро между двумя вершинами будет вести от победителя в матче между ними к проигравшему. Покрасим ребро в красный цвет, если встреча закончилась в дополнительное время, и в синий в противном случае.
Зафиксируем количество набранных очков командами и посмотрим на графы, соответствующие данному распределению очков. Среди всех таких графов выберем
граф G, в котором количество красных ребер минимально.
Лемма. В красном подграфе графа G нет следующих подграфов:
1) неориентированных циклов;
2) ориентированных путей длины 2;
3) вершин степени 3 и более;
4) неориентированных путей длины 4.
Доказательство. Покажем, как можно уменьшить количество красных рёбер, если есть описанные выше подграфы.
1. Предположим, что в G есть неориентированный красный цикл. Тогда зададим на цикле направление обхода, совпадающее с направлением одного
из рёбер, и сделаем следующую операцию: рёбра цикла, которые были ориентированы по направлению обхода, перекрасим в синий, а ориентированные против
направления цикла переориентируем по направлению. После такого преобразования распределение очков не поменяется, так как для каждой команды количество
очков во встрече с одним из соседей уменьшится на 1, а во встрече с другим увеличится на 1. Количество красных рёбер уменьшилось.
3. Предположим, что в G есть вершина A красной степени 3 или более. Тогда выберем трёх её соседей B, C, D. При этом можно считать, что все три красных ребра исходят из вершины A (случай, когда направления различны, невозможен из-за отсутствия пути длины 2, а случай трёх входящих аналогичен), а рёбра между вершинами B, C, D синие.
Не ограничивая общности, можно считать, что рёбра ведут из B в C и из C в D. Получается два случая: в первом ребро ведёт из B в D, а во втором из D в B.
Cотрём все ребра между A, B, C, D и нарисуем заново следующим образом.
Если A обыграла D, то можно изменить рёбра AB, BC, CD, AD следующим образом: рёбра AB, CD сделаем синими, а рёбра AD, BC – красными. Распределение очков не поменялось, а количество красных рёбер уменьшилось, поэтому далее можно считать, что D выиграла у A, а B выиграла у E.
Если B обыграла D, то изменим рёбра AB, AD, BC, BD, CD следующим образом: рёбра CD, DB, BA сделаем синими, а AD, BC – красными.
Если D обыграла B, то изменим рёбра BC, BD, BE, CD, DE: рёбра CB, BD, DE сделаем синими, а EB, DC – красными.
Распределение очков не поменялось, количество красных рёбер уменьшилось.
Таким образом граф на красных рёбрах без ориентации является лесом, в котором каждое дерево является цепочкой не более чем из четырёх вершин. Значит, количество красных рёбер равно 2016 – T, где T – количество деревьев в графе на красных рёбрах. Так как в каждом дереве не более четырёх вершин, T ≥ 504, то есть N ≤ 1512.
Рассмотрим турнир из четырёх команд A, B, C, D. Пусть в нём рёбра AB, AD, CD – красные, а рёбра AC, BC, BD – синие. Тогда команды A, B набрали по 7 очков, а команды C, D – по 2.
Наоборот, при таком распределении очков должно быть сыграно не менее трёх овертаймов, так как в дополнительное время должны закончиться матчи между
A и B и между C и D, так как A и B не могли проиграть в основное время, а C и D не могли победить
в основное время. Если все оставшиеся матчи завершились в основное время, то суммарное количество очков у A и B будет кратно 3, что не так.
Разобьём 2016 команд на четвёрки (A1, B1, C1, D1,), ..., (A504, B504, C504, D504). Пусть внутри четвёрок матчи закончились так, как описано выше, а при
i > j команда из i-й четвёрки побеждает команду из j-й в основное время.
Тогда из полученного распределения очков можно сделать вывод, что каждая команда из i-й четвёрки побеждает каждую команду из j-й в основное время. Действительно, команды 504-й четвёрки набрали в сумме ровно 18 очков. Поскольку в каждой игре разыгрывается три очка, все эти очки набраны в играх внутри четвёрки. Значит, команды этой чётверки проиграли всем остальным командам в основное время. Команды 503-й четвёрки набрали в сумме 18 + 12·4 очков, причём 48 очков набраны против команд 504-й четвёрки. Значит, оставшиеся 18 очков набраны внутри этой четвёрки, а всем командам из оставшихся 502 четвёрок оно проиграли в основное время. И т. д.
Кроме того, внутри каждой четвёрки будет распределение очков 7, 7, 2, 2, поэтому будет не менее трёх овертаймов, а значит, всего овертаймов не менее 1512.
Ответ
N = 1512.
