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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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