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

Пусть вершина из подграфа соединена с наименьшим количеством вершин в этом подграфе ( вершин). Предположим, что в подграфе имеется вершина , которая соединена с хотя бы вершиной из подграфа . В таком случае вершину можно переместить в подграф вместо вершины и в нём будет больше авиалиний, что противоречит выбору подграфа . Следовательно, любая вершина из подграфа связана не более чем с вершинами из подграфа .

Значит, между этими подграфами не более рёбер. Внутри же каждого из этих подграфов не более рёбер. Значит, всего в графе не более

Как известно, — это наименьшая степень вершины в подграфе . Значит, в не менее рёбер. С другой стороны, в этом подграфе не более рёбер, откуда . Теперь мы можем оценить количество рёбер в графе: .

_________________________________________________________________________________________________________________________________________________________________________________

Приведём пример на рёбер. Разбиваем города на групп по городов. Внутри групп между городами авиалиний нет, а между городами из разных групп — есть.

Пусть выбрано городов так, что из них город из первой группы, из второй, , — из -й. Тогда количество пар, не соединённых авиалиниями, будет не менее

по неравенству между средним квадратическим и средним арифметическим

Мы показали, что для произвольного подграфа в примере выполняется условие задачи.

Пусть есть 2 тройки, которые пересекаются по ребру. Назовем их и . Тогда нуо выиграл у и выиграл у , то выиграл у и , а проиграл и . Тогда выиграл у , выиграл у , выиграл у , а выиграл у ?!

Пусть есть 2 тройки, которые пересекаются по вершине. Назовем их и . Тогда без ограничения общности выиграл у и и выиграл у , то выиграл у , выиграл у , выиграл у и выиграл у . Тогда выиграл у , выиграл у , выиграл у , а выиграл у ?!

Значит, тройки не пересекаются и из не более 11. Осталось показать, что 11 троек может быть. Давайте выделим 11 непересекающихся троек и еще двойку и пронумеруем их от 1 до 14. В каждой тройке у нас будет цикл, в двойке победа будет у любого, а между группами и (где ) победа будет у группы с большим номером. Тогда если появится запретная четверка, то заметим, что если обходить ее по кругу от проигравшего к победителю, то номер группы может только расти или не изменяться. Раз мы вернемся в конце в начальную вершину, то номер группы должен все время не изменяться, и значит, все 4 вершины лежат в одной группе?! Значит, запретных четверок в таком турнире не будет.

Если стакана то побеждает Петя за один ход. Если то Вася ставит стакан рядом с Петей и сам побеждает за один ход, пусть далее

Назовём “закваской” набор из подряд идущих заполненных стаканов. Тогда Вася может увеличить размер закваски, но не может добавить новую. В то же время Петя может либо объединить две закваски, либо создать новую из одной кружки. Первым ходом Петя заполняет произвольную кружку, получая одну закваску. Назовём “застольем” набор идущих подряд по кругу заквасок. Далее пусть каждым своим ходом Петя добавляет новую закваску, пропуская один стакан после текущего конца застолья, то есть после последней закваски в нём. Пусть Петя спустя добавленных Петей заквасок не может сделать ход. Тогда всего на столе полных стаканов и не более пустых (по одному между заквасками и максимум два после конца застолья). То есть То есть найдётся хотя бы одно междузаквасье длиной один, где Петя может заполнить стакан, а Вася нет (заквасок хотя бы ). Если после застолья идёт один пустой стакан, то Вася не может сделать ход и уже проиграл (если аналогично), иначе их два. Вася заполнит один из них и второй следующим ходом сможет заполнить Петя, то есть у него есть уже два дополнительных хода, а у Васи их не осталось, потому на следующем ходу он проиграет.

Оценка.

Если нашлась вершина (город) степени не больше то она не соединена хотя бы с тремя городами. Возьмём эти три города и саму вершину, получим, что она не может быть в паре ни с одним из них, откуда степень каждой вершины хотя бы Тогда по лемме о рукопожатиях рёбер в графе не меньше

Пример.

Теперь расположим их все в вершинах правильного -угольника(!). Проведём все рёбра графа, кроме сторон самого многоугольника (то есть выкинем рёбер из полного графа). Легко проверить, что степень каждой вершины стала равна Выберем произвольную четвёрку городов и покажем, что она удовлетворяет условию задачи. Нам требуется найти их разбиение на две пары несоседних вершин — тогда внутри пар есть рёбра по построению. Но для этого достаточно соединить их через одну в том порядке, в котором они расположены в -угольнике, тогда вершины в паре разделяет ещё хотя бы одна и соседними они быть не могут.