РЕШУ ОЛИМП — математика

Задания

В однокруговом хоккейном турнире принимало участие 2016 команд. По регламенту турнира за победу дается 3 очка, за поражение 0 очков, а в случае ничьей играется дополнительное время, победитель которого получает 2 очка, а проигравший  — 1 очко. По окончании турнира Остапу Бендеру сообщили количество очков, набранных каждой командой, на основании чего он сделал вывод, что не менее N матчей закончились дополнительным временем. Найдите наибольшее возможное значение N.

Решение. Рассмотрим полный ориентированный граф, вершинами которого будут команды  — участницы турнира, в котором ребро между двумя вершинами будет вести от победителя в матче между ними к проигравшему. Покрасим ребро в красный цвет, если встреча закончилась в дополнительное время, и в синий в противном случае.

Зафиксируем количество набранных очков командами и посмотрим на графы, соответствующие данному распределению очков. Среди всех таких графов выберем граф G, в котором количество красных ребер минимально.

Лемма. B красном подграфе графа G нет следующих подграфов:

1)  неориентированных циклов;

2)  ориентированных путей длины 2;

3)  вершин степени 3 и более;

4)  неориентированных путей длины 4.

Доказательство.

Покажем, как можно уменьшить количество красных ребер, если есть описанные выше подграфы.

1.  Предположим, что в G есть неориентированный красный цикл. Тогда зададим на цикле направление обхода, совпадающее с направлением одного из ребер, и сделаем следующую операцию: ребра цикла, которые были ориентированы по направлению обхода, перекрасим в синий, а ориентированные против направления цикла переориентируем по направлению. После такого преобразования распределение очков не поменяется, так как для каждой команды количество очков во встрече с одним из соседей уменьшится на 1, а во встрече с другим увеличится на 1. Количество красных ребер уменьшилось.

2.  Предположим, что в G есть красный ориентированный путь длины 2. Тогда можно считать, что ребро между началом пути и концом  — синее. Если ребро было направлено от начала к концу, то поменяем цвет всех трех ребер, а если из конца в начало, то поменяем цвет и ориентацию всех трех ребер. Заметим, что такое преобразование не меняет количество очков, набранных командой, но уменьшает количество красных ребер.

3.  Предположим, что в G есть вершина A красной степени 3 или более. Тогда выберем трех ее соседей B, C, D. При этом можно считать, что все три красных ребра исходят из вершины A (случай, когда направления различны, невозможен из-за отсутствия пути длины 2, а случай трех входящих аналогичен), а ребра между вершинами B, C, D синие.

Не ограничивая общности, можно считать, что ребра ведут из B в C и из C в D. Получается два случая: в первом ребро ведет из B в D, а во втором из D в B.

Тогда сотрем все ребра между A, B, C, D и нарисуем заново следующим образом:

В обоих случаях рисуем синие ребра из B в A, из A в C, из A в D. В первом случае проведем красные из B в D и из B в C и синее из C в D. Во втором случае проводим красные из D в B и из D в C и синее из C в B.

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

4.  Предположим, что есть неориентированный красный путь длины 4: A, B, C, D, E. Тогда можно считать, что красные ребра ориентированы следующим образом: $\overrightarrowA B, \overrightarrowC B,$ $\overrightarrowC D,$ $\overrightarrowE D,$ а оставшиеся ребра синие.

Если A обыграла D, то можно изменить ребра AB, BC, CD, AD следующим образом: ребра $\overrightarrowA B,$ $\overrightarrowC D$ сделаем синими, а ребра $\overrightarrowA D,$ $\overrightarrowB C$   — красными. Распределение очков не поменялось, а количество красных ребер уменьшилось, поэтому далее можно считать, что D выиграла у A, а B выиграла у E.

Если B обыграла D, то изменим ребра AB, AD, BC, BD, CD следующим образом: ребра $\overrightarrowC D,$ $\overrightarrowD B,$ $\overrightarrowB A$ сделаем синими, a $\overrightarrowA D,$ $\overrightarrowB C$   — красными.

Если D обыграла B, то изменим ребра BC, BD, BE, CD, DE: ребра $\overrightarrowC B,$ $\overrightarrowB D,$ $\overrightarrowD E$ сделаем синими, а $\overrightarrowE B,$ $\overrightarrowD C$   — красными.

Распределение очков не поменялось, количество красных ребер уменьшилось.

Таким образом, граф на красных ребрах без ориентации является лесом, в котором каждое дерево является цепочкой не более чем из 4 вершин. Тогда количество красных ребер равно $2016 минус T,$ где T  — количество деревьев в графе на красных ребрах. Так как в каждом дереве не более 4 вершин, $T больше или равно 504,$ то есть $N меньше или равно 1512.$

Рассмотрим турнир из 4 команд A, B, C, D. Пусть в нем peбра $\overrightarrowA B,$ $\overrightarrowA D,$ $\overrightarrowC D$   — красные, а ребра $\overrightarrowA C,$ $\overrightarrowB C,$ $\overrightarrowB D$   — синие. Тогда команды A, B набрали по 7 очков, а команды C, D  — по $2 .$

Заметим, что при таком распределении очков должно быть сыграно не менее 3 овертаймов, так как в дополнительное время должны закончится матчи между A и B и между C и D, так как A и B не могли проиграть в основное время, а C и D не могли победить в основное время. Если все оставшиеся матчи завершились в основное время, то суммарное количество очков у A и B будет кратно 3  —противоречие.

Разобьем 2016 команд на четверки (A₁, B₁, C₁, D₁), ..., (A₅₀₄, B₅₀₄, C₅₀₄, D₅₀₄). Пусть внутри четверок матчи закончились так, как описано выше, а при $i меньше j$ команда из i-й четверки побеждает команду из j-й в основное время. Тогда из полученного распределения очков можно сделать вывод, что команда из i-й четверки действительно побеждает команду из j-й в основное время. В описанном случае внутри каждой четверки будет распределение очков 7, 7, 2, 2, поэтому будет не менее 3 овертаймов, а значит, всего овертаймов не менее 1512.

Ответ: $N=1512.$

Критерии оценивания	Балл
Полное решение	+
Неверное решение	−

№ п/п	№ задания	Ответ
1	4385	$N=1512.$

Ключ