Турниры в терминах графов и не только (считаем игры и очки)

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

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

откуда или 9.

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

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

равносильно равенству

Пусть в турнире участвовало команд. Заметим, что в каждом матче две команды в сумме получают 2 или 3 очка. Значит, общее количество очков, которые могут набрать все команды в одном круге, не меньше, чем , и не больше, чем . Из условия следует, что все команды вместе набрали в первом круге ровно в полтора раза больше очков, чем во втором ( всех очков в первом круге и во втором). Но это возможно лишь в случае, если в первом круге все матчи закончились победой одной из команд (общая сумма очков ), а во втором - ничьей (общая сумма очков ). Значит, победитель набрал во втором круге очков. По условию, , откуда находим .

Пронумеруем всех участников турнира числами от до Для любого для -го участника — количество его друзей друзей,

где — множество всех друзей -го участника. Предположим противное: каждое меньше, чем среднее количество друзей, тогда

(удвоенного количества пар друзей). Переставив слагаемые в сумме видим, что равно сумме

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

Будем доказывать это утверждение индукцией по числу участников.

База для и очевидна.

Переход: Рассмотрим турнир из го участника. Среди них выделим участников. По предположению индукции их можно занумеровать от 1 до получив цепочку, где й участник не проиграл му любое от 1 до Теперь посмотрим, куда можно “вставить” последнего го участника в данную цепочку. Начиная с 1-го, будем искать первого участника, которому проиграл й, пусть это будет участник под номером . Если от 2 до то, так как перед ним все участники проиграли му, то если вставить го между м и м, то мы получим цепочку, где каждый участник не проиграл непосредственно за ним следующему, останется их только перенумеровать. Если то го ставим в самое начало цепочки, а если й выиграл каждого из то поставим его в самый конец. Перенумеруем. Переход доказан.

Рассмотрим команду Г. Она не могла играть с командами А, Б и В из первого утверждения, не могла играть с командами Д, В и Е из второго утверждения и не могла играть с командами Ж, Д и Б из третьего утверждения. Значит, команда Г играла с командой З. Рассмотрим команду В. Она не могла играть с командами А, Б и Г из первого утверждения, не могла играть с командами Г, Д и Е из второго утверждения и не могла играть с командами Г и З, так как они играют между собой. Значит, команда В играла с командой Ж. Рассмотрим команду Д. Она не могла играть с командами Г, В и Е из второго утверждения, не могла играть с командами Ж, Б и Г из третьего утверждения и не могла играть с командами Г, З, В и Ж, так как они играют между собой. Значит, Д играла с командой А. Тогда оставшиеся две команды — Б и Е играют между собой.

Если Вова сыграл 11 игр, то общее число игр в турнире равно — а это не целое число, столько игр быть не могло.

Сыграть 14 игр Вова тоже не мог, потому что это больше, чем Андрей и Боря вместе взятые. Не играл же Вова сам с собой!

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

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

Оценка: До пересчёта у команды «Бельчата» было хотя бы на 2 очка больше, чем у команды «Метеор», а после пересчёта - хотя бы на 2 очка меньше. Кроме того, чтобы после пересчёта оказаться первой, команда «Метеор» должна иметь хотя бы одну победу. Действительно, в каждом матче разыгрывается 2 очка, поэтому если бы у команды «Метеор» не было побед, то она набрала бы не более половины возможного числа очков и не могла бы стать первой. Аналогично, для того чтобы команда «Бельчата» стала последней, у неё должно быть поражений больше, чем побед. Таким образом, после пересчёта команда «Метеор» потеряет как минимум 1 очко. Следовательно, команда «Бельчата» должна потерять не менее 5 очков, т. е. у неё должно быть не меньше пяти побед и не меньше шести поражений. Поэтому она сыграла как минимум 11 матчей, значит, в турнире участвовало не менее 12 команд.

Пример: Приведён в таблице (первой буквой В обозначен выигрыш, два последних столбца — количество очков до и после пересчета соответственно).

Команда													Сумма 1	Сумма 2
		B	B	B	B	B	0	0	0	0	0	0	15	10
	0		1	1	1	1				0	0	1	14	11
	0	1		1	1	1	0				0	1	14	11
	0	1	1		1	1	0	0				1	14	11
	0	1	1	1		1		0	0			1	14	11
	0	1	1	1	1				0	0		1	14	11
		0			0	0		1	1	1	1	1	14	11
		0	0			0	1		1	1	1	1	14	11
		0	0	0			1	1		1	1	1	14	11
			0	0	0		1	1	1		1	1	14	11
				0	0	0	1	1	1	1		1	14	11
		1	1	1	1	1	1	1	1	1	1		13	12

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

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

Из условия следует, что туров всего и в каждом матче разыгрывается как минимум очка. Оценим количество туров. Можно сказать, что и меньше туров не может быть, т.к. изначальный лидер может в оставшиеся туров потерять свое место, если будет все время проигрывать. Значит, туров больше, чем .

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

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

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

Итого: количество игр в группе по команды будет равно

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

Во время тура команд поделилось на группы. Тогда количество игр во туре — А в тур перешло команд.

Во время тура команд поделилось на группы. Тогда количество игр во туре — А в тур перешло команд.

Во время тура команды попали в одну группу, и тогда количество игр равно

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

Значит, общее кол-во игр в турнире будет равно

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

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

Если он набрал 10,5 очков, то он выиграл 10 партий и в одной сыграл вничью. Если он сыграл вничью с победителем, то у победителя не более 10,5 очков. Противоречие.

Значит, игрок, занявший второе место, набрал ровно 10 очков. В этом случае все игроки, занявшие места с восьмого по двенадцатое, проиграли все свои партии игрокам, занявшим места с первого по седьмое.

Оценка. Разрыв меньше двух очков быть не может: очки А и Я отличаются как минимум на очко от любой другой команды из восьми оставшихся команд. Кроме того, результаты остальных команд находятся строго между их результатами, потому что опять же А набрала очков больше любой другой команды, Я – меньше любой другой. Тогда между их результатами (числами очков) должно быть ещё хотя бы одно число, отсюда разница не меньше .

(a) Пример. Пусть все встречи, кроме одной, закончились вничью. Тогда победитель этой одной встречи набрал на очка больше проигравшего, а остальные расположились между ними. То есть в данном случае у команды А очков, а у команды Я – .

(b) Пример. Пусть команд (все, кроме А) выиграли друг у друга по кругу (каждая победила один раз и проиграла один раз), А победила Я, а остальные встречи закончились вничью. Тогда у А очков, у Я — очков, а у остальных — по .

В первом и третьем матче «Метеор» забросил в сумме не более шайб. Но эта сумма в раза больше числа шайб, заброшенных в первом матче, значит, она делится на . Поэтому сумма не больше . Но во втором и четвёртом матче сумма на меньше, чем в первом и третьем, так что в первом и третьем сумма хотя бы .

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

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

Если , то не выполняется условие задачи, потому что количество набранных очков – ноль. Ноль равен нулю, а не в пять раз меньше нуля.

Тогда разделим на и получим

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

Предположим, что такое могло случиться.

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

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

Значит, такое невозможно.