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

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

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

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

Первое решение.

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

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

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

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

Второе решение.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Предположим, что расстановка существует. Пусть — такое число, что — число, соседнее с Тогда существует натуральное число при котором

то есть

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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