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

Способ 1, неконструктивный. Можно для каждого n задаться вопросом — а сколько вообще мелодий длины n (без запрещённых подслов) он может сыграть? Обозначим это количество через L_n (и удобно считать, что L_0=1).

Тогда значения последовательности L_n для n<=5 это 1, 2, 4, 8, 16 и 31 (первый раз срабатывает запрет). Пока что она растёт довольно быстро — и вопрос в том, успеет ли Кощей её рост как-то «сбить».

Понятно, что последовательность длины n+1 продолжает последовательность длины n — так что для начала можно дописать к каждой мелодии длины n оба возможных продолжения. Получится 2L_n. Но при этом последние несколько нот могут образовать только что появившуюся запретную мелодию какой-то длины k. Так что для каждой запретной мелодии длины k нужно выкинуть из нашего подсчёта те, которые на неё заканчиваются. А их не больше, чем L_{n+1-k}, потому что если этот кусочек убрать — то получится разрешённая мелодия длины n+1-k.

Значит,
L_{n+1} >= 2 L_n - \sum_{k>=5} L_{n+1-k}. (*)

Важное замечание: рассуждения тут довольно универсальные. Если дудочка играет не две ноты, а d, то в формуле выше будет не 2L_n, а d*L_n. Если запрещённых подслов не по одному на длину, а какой-то список E, то будет

L_{n+1} >= d L_n - \sum_{w\in E} L_{n+1-|w|},
где |w| это длина слова w.


И теперь достаточно доказать, что последовательность L_n, удовлетворяющая неравенству (*), остаётся положительной — а, на самом деле, экспоненциально растёт.