Кощей придумал для Ивана-дурака испытание. Он дал Ивану волшебную дудочку, на которой можно играть только две ноты — до и си. Для прохождения испытания Ивану нужно сыграть какую-нибудь мелодию из 300 нот на свой выбор. Но до того, как он начнёт играть, Кощей выбирает и объявляет запретными одну мелодию из пяти нот, одну — из шести нот, ..., одну — из 30 нот. Если в какой-то момент последние сыгранные ноты образуют одну из запретных мелодий, дудочка перестаёт звучать. Сможет ли Иван пройти испытание, какие бы мелодии Кощей ни объявил запретными?
Первый способ. Пусть Ln —число мелодий длины n, не содержащих запретных последовательностей нот. Будем считать, что 
По индукции докажем, что 
для всех натуральных n.
База индукции (n = 1): 
Предположим, что неравенство 
верно для всех k, меньших n. Покажем, что тогда 
Заметим, что
Действительно, мы можем добавить одну из двух нот к уже имеющейся мелодии из n нот, при этом добавленная нота могла завершить запретную мелодию из 5 нот и испортить разрешённую мелодию из n–4 нот, завершить запретную мелодию из 6 нот и испортить разрешённую мелодию из n–5 нот и т. д. (Здесь мы можем вычесть лишнее, если 
и часть вычитаемых мелодий могут быть одинаковыми, но поскольку мы пишем оценку снизу, всё правильно.)
Из неравенства следуют неравенства
Применяя неравенства (1), (2) и (3), получим
Следовательно, 
и шаг индукции доказан. Поскольку 
и 
положительны, то из доказанного неравенства следует, что 
— возрастающая последовательность положительных чисел. Следовательно, 
и Иван справится с испытанием Кощея.
Второй способ. Рассмотрим всевозможные мелодии из нот до и си длины 13 (их 
штук
Наименьший период всех бесконечных мелодий, кроме двух, состоящих только из нот до и только из нот си, равен 13.
Количество не эквивалентных друг другу бесконечных мелодий равно 
Из них мелодий, содержащих запрещённые Кощеем мелодии, не больше
(в скобках учтены запретные мелодии длины 
за скобками — все остальные). Таким образом, найдётся бесконечная мелодия, которая не содержит запретных мелодий, и для прохождения испытания Ивану достаточно сыграть её кусок длины 300.
Ответ: да, сможет.
» — решение в целом верное, но некоторые промежуточные шаги недостаточно обоснованы.
» — решение содержит некоторые важные идеи, которых, однако, недостаточно для полного решения.