МОШ 2024, 11 класс, задача 6
Кощей придумал для Ивана-дурака испытание. Он дал Ивану волшебную дудочку, на которой можно играть только две ноты -- до и си. Для прохождения испытания Ивану нужно сыграть какую-нибудь мелодию из нот на свой выбор. Но до того, как он начнёт играть, Кощей выбирает и объявляет запретными одну мелодию из нот, одну -- из нот, ..., одну -- из нот. Если в какой-то момент последние сыгранные ноты образуют одну из запретных мелодий, дудочка перестаёт звучать. Сможет ли Иван пройти испытание, какие бы мелодии Кощей ни объявил запретными?
(В. Клепцын)
Ответ
Ответ: да, сможет.
Решение. Первый способ. Пусть -- число мелодий длины , не содержащих запретных последовательностей нот. Будем считать, что . По индукции докажем, что для всех натуральных .
База индукции : .
Предположим, что неравенство верно для всех , меньших . Покажем, что тогда . Заметим, что
Действительно, мы можем добавить одну из двух нот к уже имеющейся мелодии из нот, при этом добавленная нота могла завершить запретную мелодию из нот и испортить разрешённую мелодию из нот, завершить запретную мелодию из нот и испортить разрешённую мелодию из нот и т. д. (Здесь мы можем вычесть лишнее, если , и часть вычитаемых мелодий могут быть одинаковыми, но поскольку мы пишем оценку снизу, всё правильно.)
Из неравенства следуют неравенства
Применяя неравенства , и , получим
Следовательно, , и шаг индукции доказан. Поскольку и положительны, то из доказанного неравенства следует, что -- возрастающая последовательность положительных чисел. Следовательно, , и Иван справится с испытанием Кощея.
Второй способ (предложен участником олимпиады). Рассмотрим всевозможные мелодии из нот до и си длины (их штук). Каждую такую мелодию периодически продолжим в обе стороны, получив бесконечную в обе сторону мелодию. Назовём две получившиеся бесконечные мелодии эквивалентными, если одна получается из другой сдвигом.
Наименьший период всех бесконечных мелодий, кроме двух, состоящих только из нот до и только из нот си, равен .
Количество не эквивалентных друг другу бесконечных мелодий равно . Из них мелодий, содержащих запрещённые Кощеем мелодии, не больше
(в скобках учтены запретные мелодии длины , за скобками -- все остальные). Таким образом, найдётся бесконечная мелодия, которая не содержит запретных мелодий, и для прохождения испытания Ивану достаточно сыграть её кусок длины .