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

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

Способ 1

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

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

Способ 2

Пусть — наименьшее простое число в этом ряду большее По китайской теореме об остатках существует такое число (), что

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

Способ 3

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

количество простых меньше Из этого будет следовать, что в ряду обязательно найдутся равные числа. Пусть — количество чисел в этом ряду, кратных Подсчитаем количество чисел в ряду (*), кратных и По формуле включений-исключений это количество равно

Если то на делится каждое -ое число в ряду (*) и или Следовательно,

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

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

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

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

Оценка. Выделим все числа, минимальные в своих столбцах и все числа, максимальные в своих строках. Такие числа не могут быть седловыми. Мы хотим сказать, что выделено хотя бы число, тогда оценка будет доказана. Если это не так, то нашлось два числа и которые одновременно и минимальные в столбцах и максимальные в строках. Но тогда, Противоречие.

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

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

Рассмотрим человека, который наловил больше всего рыб, назовём его Петрович.

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

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

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

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

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

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

(а) Тогда проведем перестройку в графе (это возможно, так как ) и получим граф с По предположению, можно получить из перестройками, значит, можно получить и

(b) . Тогда — чередующийся цикл, меньший чем противоречие.

(c) Тогда проведем перестройку в графе (это возможно, так как и получим граф с По предположению, можно получить из перестройками, значит, можно получить и

(а) Для многочлена имеем

(b) Первое решение. Из условия следует, что многочлен раскладывается на линейные множители. Пусть

Тогда корнями многочлена являются числа При этом многочлен

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

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

то есть число также является корнем многочлена Но что противоречит максимальности корня Следовательно, такого многочлена не существует.

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

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

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

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

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

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

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

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

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

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

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

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

Пусть выбран некоторый максимальный набор секций.

Сделаем два замечания.

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

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

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

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

Если среди этих рёбер присутствуют рёбра ровно трёх цветов, то искомый набор найден.

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

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

Это означает, что требуемый набор вершин можно выбрать всегда.