Графы и турниры

Сначала покажем, что найдется игрок, одержавший не менее семи побед. Действительно, в противном случае общее число побед всех игроков было бы не более . Но общее число побед равно числу всех сыгранных партий, то есть равно — противоречие.

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

Заметим, что если в классе ровно человек, который поздоровался со всеми остальными, двое тех, кто поздоровались со всеми остальными, но не друг с другом, трое тех, кто поздоровался со всеми остальными, но не друг с другом, ... человек, которые пожали руку всем остальными, кроме как между собой, то будет ровно рукопожатий. Действительно, во-первых, так что группы такого размера возможны. Во-вторых, в каждой группе каждый ребёнок сделал одинаковое число рукопожатий, а дети из разных групп — разное. Но дети из одной группы как раз не жали друг другу руки, а значит условие задачи выполнено. Наконец, если построить граф знакомств на этих детях, то от полного графа его будет отличать отсутствие внунтренних ребёр в каждой группе. То есть всего рёбер будет

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

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

Заметим, что , просто потому что больше, чем рукопожатий совершить невозможно. Причём если , то по утверждению, доказанному ранее. Далее получаем, что и не больше, чем причём , так как если бы было равно хотя бы то и тоже были бы равны а таких людей по доказанному утверждению может быть не более, чем Аналогично можно доказать, что

Тогда

Но сумма, стоящая справа, равна сумме степеней вершин графа из примера, приведённого выше, а она в два раза больше количества рёбер в графе (так как сумма степеней вершин графа равна удвоенному количеству его рёбер).

Предположим, что школьник поздоровался с учениками По условию ни при каких и школьники и не здоровались друг с другом. Рассмотрим всех учеников, которые поздоровались менее раз, и выберем среди них того, кто здоровался не меньше других. Будем для определенности считать, что это и что он поздоровался раз. Тогда кроме школьник поздоровался еще с некоторыми учениками . Значит, в школе не менее учеников.

С другой стороны, по условию есть ученики, поздоровавшиеся ровно с

школьниками, и они не находятся среди Поэтому учеников в школе не меньше, чем

Таким образом, справедливы неравенства

Складывая их, мы получим

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

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

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

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

Осталось привести пример с интровертами. Давайте расположим всех их в вершинах правильного -угольника и проведём его главные диагонали. То есть интроверт в каждой из вершин будет соединён с соседями и противоположной вершиной.

Замечание. Однако при нечётном количестве участников вечеринке пример не удаётся построить, поскольку графа с нечётным количеством вершин нечётной степени не существует по лемме о рукопожатиях.

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

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

Приведем пример, показывающий, что суммарно российские шахматисты могли набрать 96 очков. Пусть Владимир выиграл все свои партии, кроме партии с Левоном, которая завершилась вничью. Пусть, кроме того, Левон сыграл вничью и со всеми остальными россиянами, а у не россиян неизменно выигрывал. Наконец, пусть все остальные партии между россиянами завершились вничью, а иностранцев, кроме Левона, все россияне победили. Тогда Владимир набрал очков, Левон набрал очков, каждый из остальных россиян набрал очков, а каждый из остальных тринадцати игроков - не более, чем 12 очков. Условие задачи в этом случае выполнено, а количество очков набранных всеми россиянами равно

Покажем, методом от противного, что больше очков россияне набрать не могут. Пусть они в сумме набрали 96,5 очков или больше. В 15-и партиях между собой они взяли в сумме 15 очков, а остальные (не менее 81,5 взяты в партиях с представителями других стран. Таких партий россиянин - не россиянин было , и в них разыгрывалось всего 84 очка. Тогда все иностранцы в партиях с россиянами набрали не более 2,5 очков, и никто из них, в том числе Левон, не мог набрать в сумме более, чем очков. Пятеро россиян, которых он опередил, набрали при этом не более 15 очков каждый, а тогда Владимир должен набрать не менее очка. Но он сыграл всего 19 партий, и потому набрать более 19 очков не мог. Противоречие.

Рассмотрим множество состоящее из всех возможных -регулярных(степени всех вершин в графе равны 100) графов на данном множестве вершин (наши две схемы дорог — среди них). Докажем что любые два графа из можно перевести друг друга серией перестроек. Для двух графов пусть - множество необщих рёбер этих графов, а . Очевидно, что число всегда четно, и в множестве поровну рёбер из и

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

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

(а) Тогда проведем перестройку в графе (это возможно, так как ) и получим граф с По предположению, можно получить из перестройками, значит, можно получить и

(b) . Тогда — чередующийся цикл, меньший чем противоречие.

(c) Тогда проведем перестройку в графе (это возможно, так как и получим граф с По предположению, можно получить из перестройками, значит, можно получить и

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

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

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

Рассмотрим вершину из которой выходит наибольшее количество одноцветных рёбер. Пусть они цвета. Пусть соединена первых цветом с Рассмотрим оставшиеся вершину, с которыми соединена другими цветами. Любая из этих вершин соединена со всеми либо первым цветом, либо тем же цветом, которым она соединена с Однако заметим, что между и вершинами, отличными от может быть не более рёбер первого цвета, поскольку есть рёбер Но, как мы выяснили ранее, имеется вершина, не соединённая с первым цветом. Значит, среди них есть одна вершина такая, что цвет всех рёбер совпадает с цветом ребра Но тогда из выходит одноцветное ребро, это противоречит выбору

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

является целым числом, следовательно,

целое число, а значит — целое, что возможно лишь при .

При матчей не было.

При число , что не является целым.

При число .

Пример: занумеруем команды числами . Команда 1 вынграла у всех, команда 2 выиграла у команды 3, команда 3 выиграла у команды 4, команда 4 выиграла у команды 2.

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

Пусть разница может быть равна Сумма всех набранных баллов равна Разобьем все команды на пары: первая-последняя, вторая-предпоследняя, и т. д., десятая-одиннадцатая. В каждой паре команды набрали одинаковое число баллов, а именно Но баллы десятой и одиннадцатой команд разной четности, поэтому такое невозможно.

Первую пару можно составить способами, вторую пару можно составить способами. Всего игр получаем Андрей всего играл в 4 парах, а они играли с 3 парами. Значит, всего Андрей играл 4×3=12 раз. По условию, он проиграл 12 раз, следовательно, он проиграл все свои игры. Вместе с ним в паре 3 раза проиграл Борис. Поскольку Борис выиграл у Андрея 6 раз, когда играл в паре с Василием (2 раза), с Геннадием, с Дмитрием, то остальные он партии проиграл, то есть 3 с Андреем и по одной с Василием (против Геннадия и Дмитрия), с Геннадием и с Дмитрием. Значит, Геннадий проиграл с Андреем 3 раза и с Борисом 1 раз, всего 4 раза. Поэтому выиграл он 8 раз.

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

Итак, почему же чёрных диаметров столько же, сколько и белых? Каждый разноцветный диаметр содержит одинаковое количество белого и чёрного цвета, потому на одноцветные приходится также равное количество этих двух цветов (изначально каждого по ). Но раз так, то количество чёрных и белых диаметров будет одинаковым, чтобы они содержали равное количество разных цветов, что и требовалось.

Построим контрпример. Разобьём города на групп по городов. Назовём эти группы

Внутри каждой группы соединим города рейсами компании номер

Компания номер будет соединять города группы с городами группы с а с

Компания номер будет соединять города группы с городами группы с а с

Компания номер будет соединять города группы с городами группы с а с

Компания номер будет соединять города группы с городами группы с а с

Компания номер будет соединять города группы с городами группы с а с

Таким образом, рейсы компании номер связывают по городов, а рейсы остальных компаний ровно по

Это построение схематически изображено на рисунке. Разные компании обозначены разными цветами.

Пусть число участников турника равно а число попавших в -ю группу равно . Тогда число сыгранных партий равно:

где

откуда

Если то:

тогда - противоречие;
- противоречие;
- противоречие;
- противоречие;
при и

Если то:

тогда - противоречие;
- противоречие;
- противоречие;
- противоречие;
при и

Если то:

тогда - противоречие;
- противоречие;
- противоречие;
- противоречие;
- противоречие;
- решение.
при и

Итак, наибольшее возможное число участников равно , группы участников насчитывают и человек, количество «межгрупповых» партий равно .

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

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

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

Оценка: назовём граф на вершинах хорошим, если при удалении любой вершины остальные вершин разбиваются на треугольников. Докажем индукцией по что в хорошем графе на вершинах хотя бы рёбер; при получим требуемую оценку. База при несложна: так как при удалении любой вершины три остальных попарно соединены, любые две вершины должны быть соединены, то есть число рёбер равно

Переход: если из каждой вершины выходит хотя бы по ребра, общее количество рёбер не меньше, чем что даже больше, чем

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

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

Рассмотрим одну из команд, обозначив ее через Так как за 8 туров она сыграла с восемью командами, то с девятью она не сыграла. Если среди этих девяти есть две команды и , не сыгравшие между собой, то и образуют искомую тройку команд.

В противном случае эти 9 команд сыграли между собой полный круговой турнир. Для этого потребовалось матчей. Однако, в каждом туре они могли играть между собой не более четырех матчей, поэтому за 8 туров таких матчей могло быть сыграно не более Полученное противоречие показывает, что искомая тройка команд обязательно найдется.

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

Рассмотрим участок Следующий город — это новый город а далее есть два варианта. Первый вариант нельзя продолжить, так как перелеты и уже были. Рассмотрим второй вариант Повторим данное рассуждение для маршрута Если мы ни разу не встретили первый вариант, то почти все буквы в данной последовательности разбились на пары. Но каждый город надо посетить — нечетное количество раз.

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