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

Нарисуем граф ходов коня, получится, что кони стоят по циклу и не могут друг “сквозь” друга пройти, следовательно, свой порядок они не изменят.

С пунктом 1) все просто: это легко сделать, если начать из нижней вершины. А вот в пункте 2) ничего не получается. Действительно ли это невозможно, или мы просто плохо стараемся? Оказывается, невозможно, и доказать это можно так.

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

Всего в турнире игр, и в каждой игре разыгрывается очка. Поэтому всего команды должны набрать очков. Команды помимо D набрали в сумме очков, значит, у D 4 очка. Это означает, что она заняла второе место.

Всего в турнире матчей. Поэтому как максимум в сумме может получиться очков. Но команды набрали на три очка меньше. Каждый раз, когда вместо победы происходит ничья, суммарное количество очков у команд уменьшается на 1. Поэтому, чтобы суммарное число очков уменьшилось на три, в турнире должно произойти ровно 3 ничьи.

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

Заметим, что при ничьей разыгрывается 4 очка, а при победе одной из команд — 5 очков. Количество очков, набранное суммарно командами в случае, когда во всех видах спорта кто-то побеждает, равно 50. В условии задачи очков 46, то есть на 4 меньше. При замене победы на ничью суммарное количество очков уменьшается на 1. Значит, в турнире было 4 ничьи.

В, Г и Д сыграли между собой 3 партии, разыграв 3 очка. Так как Б, занявший второе место, набрал больше них, то он набрал хотя бы 3,5 очка. Если бы он набрал 4, то он победил бы всех, а значит, занял бы первое место. Таким образом, Б набрал 3,5 очка. Тогда А, занявший первое место, набрал либо 4 очка, либо 3,5. Набрать 4 очка он не мог, так как тогда все остальные, в том числе Б, набрали бы не больше 3 очков. Поэтому у А тоже 3,5 очка. Значит, ни тот, ни другой не проигрывали. Тогда партия между ними могла закончиться только вничью.

Умножим все очки на 2 и будем считать, что шахматный турнир проходит по системе 2-1-0. На истинность заметки корреспондента это никак не влияет. В таком случае между командами случилось партий, в которых разыгрывалось очков.

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

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

Так как команда, занявшая 7 место, набрала 21 очко, то 6-я команда набрала хотя бы 22 очка, пятая — хотя бы 23, и так далее до первой, набравшей хотя бы 27 очков. Сложим эти очки: очков. Всего же в турнире разыгрывается очков. Команды с 8 по 16-ю сыграли между собой игр, то есть разыграли хотя бы очка. В сумме . Таким образом, никакая из команд, занявших место выше 7-го, не могла набрать больше очков, иначе сумма очков, набранных всеми командами, стала бы больше 240. Поэтому первая команда набрала ровно 27 очков, значит, хотя бы в одной из своих игр она набрала нечетное число очков, то есть сыграла вничью.

Команда «Дельта» выиграла три игры, следовательно, набрала не меньше очков. Поэтому команды «Альфа», «Бета» и «Гамма» набрали не меньше 7 очков каждая. В трех играх друг с другом они в сумме набрали очков, поэтому хотя бы одна из них в этих играх набрала не больше очков. Отсюда следует, что были ещё минимум три других команды, игры с которыми позволили ей набрать ещё минимум очков. Следовательно, всего команд не меньше семи.
Пример турнира для 7 команд:

команда	А	Б			E	Z	H	о
А		1	2	0	2	2	2	9
Б	1		1	0	2	2	2	8
	0	1		0	2	2	2	7
	2	2	2		0	0	0	6
E	0	0	0	2		1	2	5
Z	0	0	0	2	1		1	4
H	0	0	0	2	0	1		3

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

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

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

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

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

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

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

Противоречие.

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

Тогда от белых вершин выходит ребер, а от черных — ребер. А так как и то, и другое числа равны общему количеству ребер, получаем, что . Итак, целые числа и относятся, как . Поэтому существует некое целое , для которого , , а сумма . Эта же сумма и есть общее количество коней, и, как мы только что выяснили, она кратна 7.

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

Обозначим количество вершин в графе через . Тогда суммарная степень всех вершин графа равна . Эта же суммарная степень равна удвоенному количеству ребер, то есть должна быть равна 200. Но равенство невозможно при целом .