Испытание Ивана и Кощей: олимпиадная задача о запретных мелодиях

Решение 1:  Рассмотрим всевозможные мелодии из двух нот длины $p$ = 13; их 2¹³штук. Каждую из этих мелодий можно продолжить периодически в обе стороны, получая бесконечные периодические мелодии; скажем, что две такие мелодии эквивалентны, если одна из них получается из другой сдвигом. С точностью до такой эквивалентности, есть  (2¹³– 2):13 + 2 = 632  разных периодических последовательности.   Посмотрим, сколько из них содержат запретные мелодии. Поскольку мы разрешаем сдвиг – можно считать, что запретная мелодия начинается с фиксированного (например, первого) места. Поэтому из-за запретных мелодий длины $k$ = 5, 6, ..., 12 мы вычеркнем не больше 2⁸, 2⁷, ..., 2¹периодических последовательностей из нашего списка, а из-за последовательностей длины $k$ = 13, ..., 30 – не более одной. Итого запреты Кощея вычёркивают не больше (2⁹–2) + 18 = 528 последовательностей. Значит, найдётся хотя бы одна бесконечная периодическая мелодия, не содержащая запрещённых Кощеем участков, и Ивану достаточно сыграть её участок длины 300.

Решение 2:  Для каждого $n$ зададимся вопросом: а сколько вообще мелодий длины $n$, не содержащих запретных, Иван может сыграть? Обозначим это количество через $L_n$ и для удобства положим $L_0$ = 1.   Оценим рост последовательности $L_n$. Сыграв после такой мелодии из $n$ нот каждую из двух возможных нот, мы получаем 2$L_n$ мелодий длины $n$ + 1; при этом запретная мелодия в такой последовательности могла возникнуть только в конце (потому что мы предполагаем, что в первых $n$ нотах запретных мелодий нет). Если такая полученная мелодия оканчивается на запретную длины $k$, то после выкидывания этой запретной остаётся начальная часть из $n+1-k$ нот, не содержащая запретных мелодий, – поэтому таких мелодий не больше $L_{n+1-k}$. Вычёркивая из исходных 2$L_n$ мелодий длины $n$ + 1 все такие, заканчивающиеся на запретную, мелодии, окончательно получаем нижнюю оценку $$L_{n+1} \ge 2 L_n - \sum \limits_{5\le k \le n+1} L_{n+1-k}. \quad \quad(1)$$   Оценим теперь скорость роста последовательности $L_n$: докажем по индукции, что для всех $m$ ≥ 1 выполнено (Фибоначчи-подобное) неравенство $$L_{m+1}\ge L_m + L_{m-1}. \quad \quad(2)$$   При $n$ = 0, 1, 2, 3, 4 последовательность $L_n$ – это 1, 2, 4, 8, 16, поэтому (2) выполнено при $m$ = 1, 2, 3.   Пусть теперь $(2)$ выполнено для всех $m < n$, докажем его для $m=n$. Применяя $(1)$ и выполненное по предположению $(2)$ для $m=n$ – 1, получаем $$L_{n+1}-L_n-L_{n-1} \ge L_n - L_{n-1} - \sum \limits_{5\le k \le n+1} L_{n+1-k} \ge L_{n-2} - \sum \limits_{5\le k \le n+1} L_{n+1-k}.$$   Правая часть теперь оценивается с последовательным использованием предположения индукции для $m=n$ – 3, $n$ – 4, ..., 1: $$ \underbrace{L_{n-2}-L_{n-4}}{\ge L{n-3}}-L_{n-5}-L_{n-6} -\dots -L_0 \ge $$$$ \quad \ge \underbrace{L_{n-3}-L_{n-5}}{\ge L{n-4}}-L_{n-6}- L_{n-7} - \dots -L_0 \ge $$$$ \quad \quad \ge \underbrace{L_{n-4}-L_{n-6}}{\ge L{n-5}}- L_{n-7} - L_{n-8} - \dots -L_0 \ge \dots \ge{}$$$$ \quad \quad \quad \ge L_2 - L_0 \ge L_1 \ge 0.$$   Шаг индукции доказан, и тем самым утверждение (1) доказано при всех $m$. Значит, $L_n$ > 0 при всех $n$; в частности, найдётся последовательность нот длины $n$ = 300, не содержащая запретных мелодий.Вариация решения. Начав как выше, после получения неравенства (1) можно продолжить оценку другим способом. А именно, доказать по индукции, что для всех $m$ выполнено неравенство $$L_{m+1} \ge c L_m, \quad \quad (3)$$ где $c$ > 1 – некоторая константа. (Такое неравенство гарантирует экспоненциальный рост последовательности $L_n$, так что его выбор достаточно естественен.)

  Посмотрим, при каком условии на $c$ > 1 мы можем доказать (3) по индукции. А именно, предположим, что это неравенство выполнено при всех $m < n$. Тогда при всех $k$ выполнено $L_{n-k}\le \frac{1}{c^k} L_n,$ и поэтому из (1) следует, что $$L_{n+1} \ge \biggl(2-\sum_{5\le k\le n+1} \frac{1}{c^{k-1}}\biggr) L_n.$$   Для завершения шага индукции тем самым достаточно потребовать, чтобы выполнялось неравенство $$2- \sum_{k\ge 5} \frac{1}{c^{k-1}} \ge c. \quad \quad (4)$$   Сумма геометрической прогрессии в (4) равна $\frac{c^{-4}}{1-c^{-1}}$, поэтому это условие может быть переписано как $$2- c - \frac{c^{-4}}{1-c^{-1}} \ge 0,$$ или, после домножения на $c^3(c-1)$ > 0, $$c^3 (2- c)(c-1) - 1 \ge 0. \quad \quad (5)$$   Для любого такого $c$ > 1 неравенство (3) оказывается доказанным по индукции, откуда $L_n$ > 0 при всех $n$, что завершает решение задачи. Остаётся удовлетворяющую (5) константу $c$ > 1 предъявить.

  Найдём максимум левой части: приравнивание к нулю производной, после сокращения на $c^2$, приводит к квадратному уравнению $$-5 c^2+ 12 c -6=0$$ с корнем, бо́льшим единицы, $$c_=\frac{6+\sqrt{6}}{5}.$$Его подстановка приводит к значению$$c_^3 (2-c_)(c_-1) -1 = \frac{744\sqrt{6}-1721}{5^5},$$ которое положительно: $\frac{1721}{744}=2+\frac{233}{744} < 2\frac{1}{3} < \sqrt{6}$.   Замечание. На самом деле, подстановка вместо $c$ золотого сечения $\phi=\frac{1+\sqrt{5}}{2}$ обращает неравенство (4) в равенство; неравенство (5) выполнено на отрезке $[\phi,1{,}75\dots]$, и в частности для $c=\frac{5}{3}$ или $c=\frac{7}{4}$, что несложно проверить вручную: их подстановка приводит к выполняющимся неравенствам 5³·1·2 > 3⁵ и 7³·1·3 > 4⁵.