Принцип крайнего

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

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

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

Отметим, что поскольку а в классах по учеников, то (и такой Петя найдется). Если условие не выполнено, то у Пети в Б классе не более (иначе вместе с Васей у них в этом классе есть общий друг). Значит, в А классе у Пети хотя бы друг, противоречие с выбором, который был ранее сделан.

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

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

Отметим на каждом пути первую дорогу числом Теперь на каждом пути останется не менее дорог. Повторяя рассуждение, расставим отметки на каждом пути. Теперь раздадим дороги компаниям в соответствии с их “номерами”.

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

Предположим, что какие-то два из отрезков ( и ) имеют общую точку .

Применим неравенство треугольника:

Сложим эти неравенства:

Тогда если мы поменяем пары в разбиении на пары то сумма длин проведенных отрезков уменьшится. Но это противоречит минимальности суммы длин во взятом разбиении на пары.

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

Так как ось абсцисс не параллельна ни одному из отрезков между точками, у всех точек будут различные ординаты. Тогда пронумеруем точки сверху вниз. И проведём отрезки, соединяющие самые “верхние” точки, затем следующие по высоте точки и так далее. (Пример на картинке)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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