ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 65677
Темы:    [ Турниры и турнирные таблицы ]
[ Вспомогательная раскраска (прочее) ]
[ Ориентированные графы ]
[ Деревья ]
[ Принцип крайнего (прочее) ]
[ Примеры и контрпримеры. Конструкции ]
Сложность: 5
Классы: 9,10,11
В корзину
Прислать комментарий

Условие

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


Решение

  Рассмотрим полный ориентированный граф, вершинами которого будут команды – участницы турнира, а ребро между двумя вершинами будет вести от победителя в матче между ними к проигравшему. Покрасим ребро в красный цвет, если встреча закончилась в дополнительное время, и в синий в противном случае.
  Зафиксируем количество набранных очков командами и посмотрим на графы, соответствующие данному распределению очков. Среди всех таких графов выберем граф G, в котором количество красных ребер минимально.

  Лемма. В красном подграфе графа 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.
  Cотрём все ребра между A, B, C, D и нарисуем заново следующим образом.
  Распределение очков не поменялось, а количество красных рёбер уменьшилось.

  4. Предположим, что есть неориентированный красный путь длины 4: A, B, C, D, E. Можно считать, что красные рёбра ориентированы следующим образом: AB, CB, CD, ED, а оставшиеся рёбра синие.
  Если 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.

Источники и прецеденты использования

олимпиада
Название Московская математическая олимпиада
год
Год 2016
Номер 79
класс
Класс 10
задача
Номер 6

© 2004-... МЦНМО (о копирайте)
Пишите нам

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .