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

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

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

Всего у каждого из семи подписанных на канал учеников может быть не более трёх хороших друзей. Следовательно, изначально количество хороших пар не превышает 21. Рассмотрим момент, когда на канал подписались все ученики, кроме одного. Тогда в момент, когда подпишется последний ученик, количество хороших пар уменьшится уже на 3, следовательно, подписок может быть не более чем 19. Так как в классе всего 28 человек, то весь класс не может быть подписан на канал.

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

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

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

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

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

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

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

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

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

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

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

а значит, вероятность выиграть больше

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

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

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

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

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

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

откуда или 9.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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