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

  Зафиксируем количество набранных очков командами и посмотрим на графы, соответствующие данному распределению очков. Среди всех таких графов выберем граф 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 команд на четвёрки  (A₁, B₁, C₁, D₁,), ..., (A₅₀₄, B₅₀₄, C₅₀₄, D₅₀₄).  Пусть внутри четвёрок матчи закончились так, как описано выше, а при

i > j  команда из i-й четвёрки побеждает команду из j-й в основное время.

  Тогда из полученного распределения очков можно сделать вывод, что каждая команда из i-й четвёрки побеждает каждую команду из j-й в основное время. Действительно, команды 504-й четвёрки набрали в сумме ровно 18 очков. Поскольку в каждой игре разыгрывается три очка, все эти очки набраны в играх внутри четвёрки. Значит, команды этой чётверки проиграли всем остальным командам в основное время. Команды 503-й четвёрки набрали в сумме  18 + 12·4 очков,  причём 48 очков набраны против команд 504-й четвёрки. Значит, оставшиеся 18 очков набраны внутри этой четвёрки, а всем командам из оставшихся 502 четвёрок оно проиграли в основное время. И т. д.

  Кроме того, внутри каждой четвёрки будет распределение очков 7, 7, 2, 2, поэтому будет не менее трёх овертаймов, а значит, всего овертаймов не менее 1512.

N = 1512.