Применение классических комбинаторных методов к разным задачам → .10 Индукция в комбинаторике

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

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

то все пары где окажутся хорошими; таких пар всего Кроме этого, все пары вида также окажутся хорошими; таких пар всего При этом пара учтена дважды, так что общее количество хороших пар равно

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

Пусть теперь Рассмотрим произвольную шеренгу и выберем в ней хорошую пару в которой — наибольшее; пусть для определённости и ребёнок стоит левее, чем Назовём ребёнка прекрасным, если он образует хорошие пары как с так и с

______________________________________________________________________________________________________________________________________________________

Лемма. Существует не больше двух прекрасных детей.

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

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

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

_________________________________________________________________________________________________________________________________________________________________________________

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

откуда общее количество хороших пар не превосходит

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

В одной строке не менее 10 различных чисел, поэтому в следующих трех строках вместе появляется не более 5 новых чисел. Стало быть, первые четыре строки содержат не более 15 различных чисел, а каждые следующие три строки дают не более 5 новых чисел и всего чисел не больше, чем

Приведем пример на 175 чисел. Занумеруем строки числами от 1 до 100. В первой строке поставим числа от 1 до 10, а в строке с номерами от до поставим числа 1 до 5 и числа от до Тогда в каждой строке будет 5 уникальных чисел и еще числа от 1 до 5, т.е. ровно 10 различных чисел, а в каждых четырех строках будет ровно 15 различных чисел. Таким образом, в таблице будут числа от до

Замечание.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

База индукции. — что верно.

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

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

Итого, утверждение доказано. В -ую секунду у нас бактерий. А значит, через ровно через секунд все бактерии будут уничтожены.

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

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

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

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

Легко видеть, что

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

Аналогично

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

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

при . Тогда

при всех , в том числе и при .

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Пример. Отметим в третьей, шестой, девятой, , 48 строках все клетки в столбцах, номера которых не дают остаток 1 при делении на 3. Тогда в каждой из этих 16 строк отмечено по 33 клетки — всего клеток.

Оценка. Докажем методом математической индукции, что на доске меньше клеток отметить нельзя. База для очевидна.

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

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

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

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

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

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

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

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

что противоречит нашему предположению.

_________________________________________________________________________________________________________________________________________________________________________________

Второе решение. Приведём другое доказательство того, что длина хорошего слова не превосходит Индукция по В базовом случае буквы в слове чередуются, и слово длины хотя бы содержит фрагмент вида из которого вычёркиванием букв можно получить Для перехода предположим, что в -буквенном алфавите есть хорошее слово длины, не меньшей Тогда какая-то буква встречается в этом слове хотя бы три раза. Предположим, что букв, встречающихся хотя бы раза, две — и Пусть, без ограничения общности, второе вхождение стоит раньше второго вхождения тогда вычёркиванием букв можно получить слово что невозможно. Значит, буква встречается в слове раз, а все остальные — максимум по два раза. Тогда длина слова не меньше, чем и не больше, чем откуда Между вторым и третьим вхождением буквы есть какая-то буква Эта буква не может встречаться в других местах: если она встречается после второго вхождения то вычёркиванием букв можно получить а если до него — то (поскольку Пусть соседи буквы различны. Тогда, удалив её из слова, мы получим хорошее слово в -буквенном алфавите (без буквы Длина этого слова будет не меньше что противоречит индукционному предположению. Если же соседи буквы одинаковы, удалим из слова и букву перед ней; тогда на этом «стыке» останутся различные буквы. Поэтому мы опять получим хорошее слово в -буквенном алфавите, длина которого не меньше, чем это опять же невозможно по индукционному предположению.

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

База индукции: при перебором убеждаемся, что .

Переход: Пусть неравенство верно для карточек каждого цвета. Докажем, что оно верно, если количество карточек каждого цвета равно . Рассмотрим, как может увеличиться сумма , если добавить по одной карточке каждого цвета.. Без ограничения общности можно считать, что белая карточка добавлена на самый верх стопки, а добавленные чёрная и красная карточки - самые верхние среди карточек своего цвета. Пусть выше первой сверху красной карточки расположено ранее лежащих чёрных, а выше первой сверху чёрной — ранее лежащих белых. Тогда белая карточка добавляет в сумму (учитывая все чёрные, лежащие под ней), чёрная карточка добавляет (учитывая все красные, лежащие под ней) и w, за счёт того, что она лежит под w старыми белыми карточками, а красная карточка добавляет не более, чем за счёт белых, лежащих под ней, и за счёт того, что она лежит под старыми чёрными карточками. Итого, . Учитывая, что , получим: .

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

Первое решение. Обозначим Назовём последовательность из натуральных чисел, любые два соседних члена которой различаются не больше, чем на 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 другой стороны по условию оно пересекается с множествами).

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

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