Ещё другой способ рассуждать — удивительным образом, приводящий к такому же неравенству (и у меня нет этому хорошего объяснения).

Прошлое решение было неконструктивным — мы посчитали разрешённые последовательности длины n, и выяснили, что их число всегда положительно (и даже быстро растёт). Но это не позволяет ответить на вопрос «а как же Ивану играть» (ну, если исключить рекомендации вида «ну, обходи дерево мелодий, рано или поздно на разрешённую наткнёшься»).

Давайте представим себе Ивана, играющего мелодию ноту за нотой. Ему нужно решить — какую ноту играть следующей?

Логично, что Иван не хочет проиграть, сыграв одну из запретных мелодий. И логично, что он следит за тем, какие ноты ему сейчас опасно играть: если последние сыгранные 13 нот это первые 13 из запретной мелодии длины 15 — то ему, конечно, было бы логично следующей нотой сыграть не ту, которая идёт 14-й в запретной мелодии. А как бы это устроить?

Давайте измерять «опасность», происходящую от ситуации «ещё вот эти k нот сыграть приводит к проигрышу», величиной a^k, где a — некоторая константа, 0<a<1.
Теперь рассмотрим сумму всех опасностей: для каждого запрета и для каждого способа этот запрет «приложить» к уже сыгранной мелодии, если остаётся ещё k нот, возьмём величину a^k и все такие величины сложим. Обозначим эту сумму для сыгранной мелодии w через S(w).

Теперь пусть Иван на каждом шаге выбирает ту ноту j, после которой сумма опасностей S(wj) оказывается наименьшей. Если эта сумма опасностей каждый раз оказывается меньше 1 (соответствующей пустому слову, a^0) — значит, ни одна запретная мелодия не сыграна, и Иван выигрывает.

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

Так вот — посмотрим на сумму опасностей S(wj) по всем нотам j. Во-первых, каждый хвостик запрета, если мы сыграем ту ноту j, с которой он начинается, становится на одну ноту короче, а если (любую) другую, то исчезает. Так что в итоге тут сумма поделится на a.

Во-вторых, в каждом запрете мы можем сыграть первую ноту. Итого — сумма a^{|u|} по всем запретам u, опять же, делённая на a, потому что первая нота уже сыграна.

Итого
\sum_j S(wj) <= (S(w) + \sum_u a^{|u|}) / a.

Это — просто сумма. Значит, для среднего арифметического

(1/n) \sum_j S(wj) <= (S(w) + \sum_u a^{|u|}) / (da).

Так что найдётся нота j, для которой

S(wj) <= (S(w) + \sum_u a^{|u|}) / (da).

Остаётся выяснить, что мы не «перепрыгнем» через 1 — точнее, найти, при каком условии это можно гарантировать. Оценка на новое значение S(wj) линейно (и потому монотонно) зависит от старого, так что достаточно посмотреть, что 1 переходит в значение, меньшее 1, то есть что

1 < (1+\sum_u a^{|u|}) / (da).

Домножим на na, перенесём 1 в другую часть, получаем

\sum_u a^{|u|} < da -1. (***)

Так вот — на самом деле, (***) это то же самое неравенство, которое мы видели раньше, когда оценивали рост числа последовательностей L_n,

d - \sum_u c^{-(|u|-1)} >= c,

только написанное в терминах a=1/c и поделенное на a.
И достаточно предъявить одно a, для которого для длин запретов, установленных Кощеем (по одной мелодии длин 5,6,…), оно будет выполнено — и это даёт Ивану явный (и довольно эффективный) алгоритм, как играть сколь угодно долго.