Лемма о рукопожатиях

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

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

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

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

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

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

Нечётных степеней среди них

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

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

Значит у каждого рыцаря не более друзей, а также у каждого рыцаря ровно врага, значит,

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

Разберём случаи:

1.

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

2.

Полный красный граф на вершинах.

3.

Но у каждого рыцаря по врага. Значит, не подходит.

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

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

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

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

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

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

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

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

Оценка.

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

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

Пример.

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

Оценка.

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

Пример.

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

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

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