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

За­фик­си­ру­ем ко­ли­че­ство на­бран­ных очков ко­ман­да­ми и по­смот­рим на графы, со­от­вет­ству­ю­щие дан­но­му рас­пре­де­ле­нию очков. Среди всех таких гра­фов вы­бе­рем граф 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. Тогда можно счи­тать, что крас­ные ребра ори­ен­ти­ро­ва­ны сле­ду­ю­щим об­ра­зом: а остав­ши­е­ся ребра синие.

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

Если B обыг­ра­ла D, то из­ме­ним ребра AB, AD, BC, BD, CD сле­ду­ю­щим об­ра­зом: ребра сде­ла­ем си­ни­ми, a   — крас­ны­ми.

Если D обыг­ра­ла B, то из­ме­ним ребра BC, BD, BE, CD, DE: ребра сде­ла­ем си­ни­ми, а   — крас­ны­ми.

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

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

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

За­ме­тим, что при таком рас­пре­де­ле­нии очков долж­но быть сыг­ра­но не менее 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-й в ос­нов­ное время. В опи­сан­ном слу­чае внут­ри каж­дой чет­вер­ки будет рас­пре­де­ле­ние очков 7, 7, 2, 2, по­это­му будет не менее 3 овер­тай­мов, а зна­чит, всего овер­тай­мов не менее 1512.

Ответ: