Индукция в комбинаторике

Первое решение.

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

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

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

Из них мелодий, содержащих запрещённые Кощеем мелодии, не больше

(в скобках учтены запретные мелодии длины , полученные дописыванием символов к запретной мелодии длины , а за скобками — все остальные).

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

______________________________________________________________________________________________________________________________________________________

Второе решение.

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

База индукции

Предположим, что неравенство верно для всех , меньших Покажем, что тогда Заметим, что

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

Из предположения индукции для также следуют неравенства:

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

Следовательно, и переход доказан.

Тогда из-за положительности последовательность возрастающая, а значит , откуда следует, что Иван справится с испытанием Кощея.