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

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

Обозначим через сумму денег, на которую Паша стал богаче (а Игорь - беднее) по результатам всех игр.

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

Если то сразу же получаем серию из одного выигрыша такой же суммы

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

По условию, Но все числа от 901 до 998 содержат в двоичном представлении поэтому Паша выиграл и игры. При этом есть и последняя игра под номером 9, которую Паша тоже должен был выиграть (как мы отметили в начале решения). В итоге Паша выиграл хотя бы 4 игры.

Кроме этого, за первые 6 игр Паша должен был выиграть хотя бы 3 раза:

1.

из первых четырёх игр выиграна хотя бы одна, так как

2.

из двух следующих также выиграна хотя бы одна, так как

3.

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

Таким образом, суммарно Паша выиграл не менее игр.

Пример для игр: изначально у Паши было рублей, у Игоря – рублей, всего сыграно 10 игр. Тогда

Значит, Паша выигрывал в играх с номерам а Игорь – в играх В конце у Паши окажется рубля, а у Игоря – рублей.

Рассмотрим фиксированную арифметическую прогрессию длины . Заметим, что она присутствует ровно в различных раскрасках. Заметим, что всего таких прогрессий с разностью не больше , с разностью ещё меньше и так далее. Максимальная разность меньше . Итого всего прогрессии “портят” менее раскрасок. Значит, есть хотя бы одна не испорченная раскраска (поскольку всего раскрасок как раз ).

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

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

1)
Тогда ни один юноша с ростом не сможет танцевать ни с одной девушкой с ростом Но тогда последние юношей могут танцевать не более с чем девушками, противоречие.

2)
Тогда ни один юноша с ростом не сможет танцевать ни с одной девушкой с ростом Но тогда первые юношей могут танцевать не более с чем девушками, противоречие.

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

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

Разложим коробки от меньшей к большей. Предположим, что в третьей с начала коробке меньше 10 фигурок. Тогда всего в первых трех коробках не больше фигурок — противоречие. Значит, в третьей коробке хотя бы 10 фигурок. Аналогично показывается, что третья коробка с конца содержит не больше 15 фигурок(). Предположим, что эта коробка содержит 14 фигурок или меньше. Тогда суммарное количество фигурок в коробках, отличных от первых трёх и последних трёх, не превосходит , а должно быть . Противоречие. Значит, в третьей с конца коробке ровно 15 фигурок. Тогда в самой большой коробке может быть либо 18 (), либо 19 () фигурок. Больше 19 фигурок быть не может, потому что тогда во второй по величине коробке фигурок не больше, чем а в ней хотя бы 16 коробок. Меньше 18 быть не может, так как тогда фигурок в трех самых больших коробках не больше, чем Оба ответа подходят: (7,8,10,11,12,14,15,17,18) и (7,8,10,11,12,14,15,16,19).

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

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

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

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

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

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

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

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

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

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

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

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

База для В первую кучу положим и во вторую и в третью — и в четвёртую — и Остальное — в пятую.

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

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

Докажем индукцией по

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

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

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

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

Предположим, что показания разные. По рассуждениям из базы ясно, что такая ситуация даёт нам понять, какая из кучек содержит фальшивую монету. Заметим, что теперь у нас монет и взвешивания, то мы можем использовать предположение. Что и требовалось.

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

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

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

(a) Пусть и  – положения конца минутных стрелок часов с номером в моменты и минут,  – центр -х часов, а  – центр стола.

Лемма. для любого

Доказательство. Рассмотрим треугольник с вершинами Ясно, что  – его медиана. Как известно, медиана треугольника не превосходит полусуммы прилежащих к ней сторон (достаточно достроить треугольник до параллелограмма и применить неравенство треугольника к ).

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

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

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

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

Объясним эту формулу. Разобьем время на максимальное число полных оборотов () и то что осталось – интервал от до Поскольку  – разность между средним расстоянием от конца минутной стрелки до за один оборот часов и то за оборотов средняя разность будет равна а суммарная разность . Ясно, что среднее расстояние от конца минутной стрелки до за время от 0 до равно среднему расстоянию за время от до поэтому средняя разность расстояния от конца минутной стрелки до и за это время равно а суммарное – Итак, в числителе стоит суммарная разность за время и ее мы делим на чтобы получить среднюю.

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

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

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

Теперь перейдем к случаю произвольного Оценим среднее количество ребер в подграфе на вершин. Достаточно найти сумму количества ребер во всех таких подграфах и поделить на их количество: А первое можно вычислить альтернативным способом: как сумму по всем ребрам числа подграфов размера его содержащих. Это число не превосходит Если ребро фиксировано, то чтобы дополнить его до подграфа размера необходимо выбрать ровно среди оставшихся Итак,

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