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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

(b) Если чётное, то Петя может первым ходом разделить конфеты на кучки из и конфет. Поскольку нечётное, то Петя выиграет, играя по стратегии Васи для нечётного

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

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

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

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

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

Упорядочим баллоны по весу: Баллоны с нечётными индексами поместим в первый грузовик, баллоны с чётными — в другой. Заметим, что

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

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

а с другой стороны

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

Произвольно занумеруем коробки. Обозначим за — количество яблок в коробке с номером за — количество груш в коробке с номером

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

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

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

Произвольно занумеруем коробки. Обозначим за количество яблок в коробке с номером за — количество груш в коробке с номером

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

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

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

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

Таким образом, и откуда Получили противоречие с неравенством

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

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