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

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

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

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

Всего до того, как останется одно число, сделано шагов, поэтому в конце будет

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

Все члены разностной последовательности равны 0, или так что количество всевозможных разностных последовательностей равно

Посчитаем сначала количество всех интересных последовательностей, минимальный член которых не превосходит 5. Рассмотрим произвольную разностную последовательность Любые две интересные последовательности, соответствующие ей, отличаются прибавлением одного и того же числа к каждому члену. Значит, среди них ровно по одной последовательности с минимальным членом, равным 1, 2, 3, 4 или 5. Таким образом,

В учтены все последовательности, выписываемые Петей, и несколько лишних — тех, в которых не встречается ни 4, ни 5. Ясно, что, если в интересной последовательности встречаются как числа, большие 5, так и меньшие 4, то 4 или 5 также встретится. Но минимальный член каждой лишней последовательности не больше 3, значит, и все их члены не превосходят 3. Итак, все лишние последовательности состоят из чисел 1, 2 и 3. С другой стороны, каждая последовательность из чисел 1, 2 и 3 является интересной и, стало быть, лишней.

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

______________________________________________________________________________________________________________________________________________________

Второе решение. Назовём хорошей последовательность из натуральных чисел, в которой хотя бы раз встречается число 4 или 5, а любые два соседних члена различаются не больше, чем на 2. Обозначим через количество хороших последовательностей длины Мы докажем индукцией по что База индукции при очевидна.

Сделаем переход от к Рассмотрим произвольную -членную хорошую последовательность; пусть она оканчивается числом Тогда к ней можно приписать любое число от до полученная последовательность будет хорошей, если приписываемое число натуральное. Если же оно неположительно (то есть равно 0 или то после приписывания прибавим ко всем числам последовательности по 5. Полученная последовательность будет оканчиваться числом 4 или 5, а значит, будет хорошей.

Заметим, что все полученные последовательности — разные. Для последовательностей, полученных без прибавления 5, это очевидно; при этом таким образом получаются ровно все хорошие последовательности, среди первых членов которых есть 4 или 5. Последовательности же, полученные прибавлением 5, также попарно различны; при этом это — ровно все хорошие последовательности, первые членов которых больше 5, и при этом среди них встречается 9 или 10. В частности, эти последовательности отличны от описанных ранее. Итого, мы уже построили хороших -членных последовательностей.

Осталось подсчитать число ещё неучтённых последовательностей. В каждой неучтённой последовательности среди первых членов нет чисел 4, 5, 9 и 10, а последний член равен 4 или 5. Значит, либо первые её членов — единицы, двойки и тройки, либо все они — шестёрки, семёрки или восьмёрки. Посчитаем количество первых; количество вторых считается аналогично.

Рассмотрим любую последовательность из единиц, двоек и троек (её соседние члены автоматически отличаются максимум на 2). Если она оканчивается числом 3, то к ней можно приписать 4 или 5, получив неучтённую последовательность. Если она оканчивается числом 2, то можно приписать лишь 4; если же её последнее число — 1, то хорошую последовательность из неё получить нельзя. Значит, количество полученных неучтённых последовательностей равно (и ещё столько же получаются из последовательностей с числами 6, 7 и 8).

Итого, мы получаем

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

Пусть выбран некоторый максимальный набор секций.

Сделаем два замечания.

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

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

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

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

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

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

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

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

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

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

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

База при очевидна.

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

— посчитали все элементы выкинутого множества.

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

Тогда по ранее проведённым рассуждениям при возврате выкинутого множества сумма из условия увеличится на

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

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

Если среди этих рёбер присутствуют рёбра ровно трёх цветов, то искомый набор найден.

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

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

Это означает, что требуемый набор вершин можно выбрать всегда.

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

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

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

Пусть, скажем, Антоново слово из букв и разрезается на палиндромы и Пусть и — слова, полученные заменой на Если слово непусто, то и — палиндромы, слово начинается с и поэтому — тоже палиндромом. Тогда Антоново слово разрезается на палиндромы и Если же слово пусто, то ( — палиндром) является требуемым разбиением. Доказательство для Борисового слова аналогично.

Индукция по толщине колоды. База (колода из одной карты) очевидна.

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

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

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

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

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

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

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

Заметим, что каждое из чисел от до встречается ровно раза: один раз оно записано синим карандашом и один — красным. Предположим, что среди чисел нет какого-то числа Тогда синее и красное находятся среди

Сотрём все красные числа — остались синие от до записанные в порядке возрастания, и среди них есть синее До него записаны числа от до то есть ровно число.

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

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

Значит, предположение было неверным, и среди чисел есть все числа от до

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

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

откуда так как

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

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

База. При на первом месте уже стоит число 1.

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

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

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

База для верна.

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

Докажем индукцией по , что можно так выкладывать гири.

База: . Для одной гири, очевидно, верно. Кладем ее на ту чашу, которая должна перевесить.

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

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

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

Следовательно, выложили гири в соответствии с алгоритмом. Переход доказан.

Решение: 1 Заметим, что за каждый ход у нас количество монет увеличивается на . Выпишем первые числа, которые будем получать: . Давайте докажем, что все числа, которые мы можем получить, меняя монеты , нечетные. Действительно, изначально монета одна, число монет нечетное. Каждый раз число монет увеличивается на четное число (на ), поэтому четность количества монет не поменяется и останется нечетной. Так как – четное, его получить нельзя.

Решение 2: Заметим, что количество монет дает остаток при делении на . Действительно, изначально монета одна, а дальше за одну операцию мы прибавляем монеты к нашему количеству, что не меняет остаток при делении на . Но дает остаток ноль при делении на , таким образом, это количество получиться не могло.

Мысль: Если вы сходу не видите какой-то инвариант, но при этом вы можете сделать первые несколько действий – сделайте, не надо просто сидеть и смотреть на задачу:)