Применение классических комбинаторных методов к разным задачам

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

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

Заметим, что минимум этого выражения достигается при или поскольку нечётно, а — целое. Тогда просуммируем по ученикам эту величину. Получим

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

Тогда То есть ЧТД.

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

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

Этап — от первого до последнего перемещения нижнего диска. Одного шага достаточно: после первого перемещения нижний диск можно больше не трогать.

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

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

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

1.

Для каждой перестановки определим индикаторную случайную величину:

Математическое ожидание равно вероятности того, что все дуг пути направлены корректно:

2.

Обозначим через общее количество гамильтоновых путей в турнире

Тогда математическое ожидание:

3.

Поскольку среднее значение равно существует хотя бы один турнир для которого:

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

Рассмотрим случайное равномерное распределение на множестве всех пар жителей. Для произвольного жителя вероятность не быть знакомым ни с одним из двух случайно выбранных кандидатов:

где — количество знакомых

Подставляя

Следовательно, вероятность участия в выборах:

Пусть — число голосующих. Тогда:

Поскольку математическое ожидание не менее существует конкретная пара кандидатов, для которой

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

Для любого множества из вершин вероятность, что все рёбра в одного цвета:

Тогда

Оценим:

Следовательно, существует раскраска, при которой нет одноцветной клики размера

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

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

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

то есть

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

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

то есть не больше

Противоречие.

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

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

Выберем наименьшее такое что

Если теперь

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

в силу выбора Покажем, что сумма

подходит.

Во-первых, все слагаемые этой суммы в нашем ряду стоят подряд.

Во-вторых, по условию. Обозначим

Тогда и, следовательно,

Остается доказать, что эта сумма не превосходит Для этого используем знание о том, что Тогда

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

_________________________________________________________________________________________________________________________________________________________________________________

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

Доказательство. Индукция по База при проверяется легко: надо провести прямую, содержащую две оставшихся точки, кроме

Для перехода рассмотрим сторону -треугольника, на которой не лежит Если прямая, содержащая эту сторону, не проведена, то все отмеченных точек на этой прямой должны быть покрыты различными прямыми; это невозможно, так как прямых Значит, эта прямая проведена. Выкинув её и точки -треугольника, лежащие на ней, получаем -треугольник, в котором проведено прямых с теми же условиями. Осталось применять предположение индукции.

_________________________________________________________________________________________________________________________________________________________________________________

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

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

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

Теперь покажем, что такое дерево существует, для этого докажем лемму.

_________________________________________________________________________________________________________________________________________________________________________________

Лемма. Есть 2 четвёрки чисел

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

Доказательство. Разберем несколько случаев:

Если не умаляя общности и можно сгруппировать

В случае и н.у.о. группируем

сводится к предыдущему, если мы перейдем к четверкам чисел

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

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

_________________________________________________________________________________________________________________________________________________________________________________

Построив снизу вверх так первые уровня дерева, мы в итоге получим четверку различных чисел

далее рассмотрим вершины со значениями(и соответствующими потомками) и и последнем шаге сложим уже эти два числа, получив в корне.

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

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

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

Возьмем дроби вида и дроби вида Поскольку то

Посчитаем сумму этих дробей:

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

откуда и противоречие.

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

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

то все пары где окажутся хорошими; таких пар всего Кроме этого, все пары вида также окажутся хорошими; таких пар всего При этом пара учтена дважды, так что общее количество хороших пар равно

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

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

______________________________________________________________________________________________________________________________________________________

Лемма. Существует не больше двух прекрасных детей.

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

Предположим, что есть два прекрасных ребёнка стоящих левее тогда

Ребёнок не может стоять между и иначе пара не хорошая; поэтому стоит левее Но тогда стоит между и и пара — не хорошая, что невозможно. Это противоречие показывает, что левее стоит не более одного прекрасного ребёнка. Аналогично, не более одного стоит правее откуда и следует доказываемое утверждение.

_________________________________________________________________________________________________________________________________________________________________________________

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

откуда общее количество хороших пар не превосходит

что и требовалось доказать.

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

Рассмотрим следующие групп, состоящих из белых отрезков каждая: при группа состоит из отрезков …, а при

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

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

Поэтому отрезок учтён хотя бы в числах вида Поэтому

Из полученных двух оценок на сумму вытекает, что

что и требовалось доказать.

_________________________________________________________________________________________________________________________________________________________________________________

Второе решение. Предположим, что утверждение задачи для некоторых неверно:

и при этом условии сумма — минимальная возможная.

Без ограничения общности тогда Возьмём -й слева белый отрезок и -й слева чёрный отрезок У какого-то из них правый конец левее.

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

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

Положим

и

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

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

Противоречие.

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

Обозначим количества карандашей разных цветов за

Если то получаем противоречие с выводом выше. Значит,

Тогда суммарно в коробке карандашей

Может ли быть ровно 1603 карандаша? Да, например, если было 19 карандашей одного цвета ( и по 16 карандашей всех остальных цветов (

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

Приведем пример на 175 чисел. Занумеруем строки числами от 1 до 100. В первой строке поставим числа от 1 до 10, а в строке с номерами от до поставим числа 1 до 5 и числа от до Тогда в каждой строке будет 5 уникальных чисел и еще числа от 1 до 5, т.е. ровно 10 различных чисел, а в каждых четырех строках будет ровно 15 различных чисел. Таким образом, в таблице будут числа от до

Замечание.

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

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

Следовательно,

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

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

Докажем, что слово имеет то же значение, что и слово из букв Если для такой пары оказывается, что то это верно. В противном случае при

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

Тогда:

Что и требовалось доказать.

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

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