Применение классических комбинаторных методов к разным задачам → .05 Принцип крайнего

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

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

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

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

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

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

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

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

Рассмотрим трёх грибников, собравших вместе максимальное (среди всевозможных троек грибников) количество грибов. Если минимальное (из этих трех) количество грибов не меньше 16, то вместе три грибника собрали грибов не меньше, чем Если указанное минимальное количество не больше 15, то оставшиеся четыре грибника собрали вместе не более грибов. Отсюда заключаем, что первые трое собрали вместе не менее 50 грибов.

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

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

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

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

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

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

Посмотрим, где стоят числа 1 и 64. Заметим, что между этими клетками есть путь, проходящий по соседними по стороне клеткам, имеющий длину не более 14. Предположим, что в любой паре соседних клеток числа отличаются не больше чем на 4. Тогда пройдя по пути от 1 до клетки, где стоит 64, мы получаем, что число в данной клетке не больше, чем — противоречие.

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

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

Заметим, что максимальная возможная сумма 29 чисел это , а минимальная возможная сумма 71 числа это . Значит сумма 71 числа всегда будет больше.

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

Предположим противное. Пусть наборы

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

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

Сопоставляя это с неравенством заключаем, что в проделанных подсчётах все оценки являются равенствами. В частности, имеется в точности верных неравенств вида а в каждой тройке ровно два верных неравенства.

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

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

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

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

Рассмотрим кружок в который входит наименьшее количество учеников, большее Заметим, что любой другой кружок либо включает в себя всех участников либо не пересекается либо является кружком по топологии. Если пересекается с каким-то кружком и не входит в него целиком, то существует кружок, в который ходят все ученики пересечения, но он меньше противоречие. Для любого кружка непересекающегося с cуществует кружок Сопоставим кружку кружок а любому другому кружку непересекающемуся с — кружок Возможно, какие-то кружки, включающие остались без пары. Это даёт понять, что кружков, включающих в себя не меньше, чем кружков, не пересекающихся с В есть хотя бы один человек, по вышеописанным рассуждениям именно он подходит под условие, что и требовалось.

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