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

Пусть клетка с координатами имеет вес тогда в процессе сумма весов клеток для каждой фишки не изменяется, ведь

Предположим, что мы добились того, что в этих трёх клетках нет фишек. Изначально сумма весов была равна 2. По итогу она меньше, чем сумма весов всех клеток, кроме этих трёх. Если считать по столбцам, то эта сумма равна:

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

Но тогда получаем противоречие, ведь сумма весов не могла стать меньше 2. А значит, требуемое доказано.

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

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

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

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

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

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

фигур, то есть она разрезает как минимум шесть -тетрамино на две фигурки из двух клеток.

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

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

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

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

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

(a) Достаточно найти несколько чисел, которые в сумме равны Упорядочим числа в порядке возрастания. Рассмотрим сумму, я сумма равна сумме наименьших чисел. Если какая-то из них делится на то она равна и задача решена, потому что эти суммы меньше Если же никакая не делится, то найдутся две суммы с одинаковыми остатками при делении на потому что без остатков Рассмотрим разность этих сумм, она делится на а значит равна Снова получили требуемое.

(b) По условию не все числа равны Отсюда следует, что хотя бы одно число равно Действительно, если все числа не меньше и хотя бы одно число строго больше, то сумма будет строго больше

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

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

откуда или 9.

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

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

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

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

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

Обозначим Тогда

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

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

Если мы проделаем аналогичные рассуждения для других пяти положений а потом сложим, то в сумме получится

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

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

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

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

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

Из первого условия следует, что ровно у точек оба соседа белые, а из второго — что ровно у точек оба соседа черные. Это означает, что у оставшихся точек соседи разного цвета.

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

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

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

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

Остальные выражаются аналогично. Тогда часов.

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

Ясно, что у каждого есть одинаковое количество друзей, обозначим его через Рассмотрим ребёнка и его друзей.

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

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

Этим решениям соответствуют и Примеры строятся в соответствии с решением: групп по ребят. Внутри групп ребята дружат, а ребята из разных групп враждуют.

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

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

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

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

(b) Аналогично предыдущему пункту покажем, что процесс не может продолжаться бесконечно. Пусть камень, лежащий в клетке с номером имеет вес (число Фибоначчи). Тогда операция не меняет сумму весов, а финале получится запись исходной суммы весов в фибоначчиевой системе счисления.

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

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

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

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

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

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