Про задачу 11-6 с сегодняшней ММО
Кощей придумал для Ивана-дурака испытание
Он дал Ивану волшебную дудочку, на которой можно играть только две ноты — до и си
Для прохождения испытания Ивану нужно сыграть какую-нибудь мелодию из 300 нот на свой выбор
Но до того, как он начнёт играть, Кощей выбирает и объявляет запретными одну мелодию из пяти нот, одну — из шести нот, …, одну — из 30 нот
Если в какой-то момент последние сыгранные ноты образуют одну из запретных мелодий, дудочка перестаёт звучать
Сможет ли Иван пройти испытание, какие бы мелодии Кощей ни объявил запретными?
Понятно, что вместо мелодий можно говорить про слова из двух символов — например (чтобы не говорить « до » и « си »), из 0 и 1
Для начала — а что, если Кощей начинает запрещать не с длины 5, а с длины 3?
Оказывается, что тогда он может выиграть!
Действительно: пусть он сначала запретит слово 001
Тогда за двумя нулями может идти только третий — и значит, только последовательность из одних нулей
Так что пара запретов 001 + 000000000000 практически равносильна запрету просто на два нуля
(Практически — потому что если мы говорим о словах конечной длины, то там незадолго до конца написать короткий хвост из нулей будет можно, но 300 это достаточно большая длина, чтобы всё закончилось до того)
Пусть Кощей эти два запрета (001 + 000000000000) и наложит
Итак, два нуля запрещены, значит, за каждым нулём следует единица
Теперь Кощей запрещает 1101
Поскольку за нулём должна следовать единица — это более-менее то же самое, что запретить просто 110
И поэтому за двумя единицами будет следовать третья — так что, добавив к этому запрету 1111111111, Кощей добивается того, что и две единицы подряд запрещены
За 0 следует 1, за 1 следует 0, теперь Кощей запрещает 01010 — и испытание становится непроходимым
(Кстати, последовательности из 0 и 1 выше можно сократить до длин 6 и 7 соответственно — там они длинные, чтобы показать, что в этом месте можно обойтись и очень длинным запретом)
Если вернуться к исходному условию — то, как и положено, Иван-дурак может выиграть
И тут есть разные решения
Способ 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, удовлетворяющая неравенству (*), остаётся положительной — а, на самом деле, экспоненциально растёт
Очень логично было бы доказывать, например, неравенство экспоненциального роста:
L_{n+1} >= c*L_n,
где c>1 — какая-то (хорошо выбранная) константа
Разумеется, доказывать — по индукции
Потому что если L_n экспоненциально растёт, то вычитаемые L_{n+1-k} должны оказываться «маленькими» по сравнению с уже имеющимся L_n
И действительно: если у нас L_m >= c L_{m-1} при m<=n, то
L_{n+1-k} <= L_n / c^{k-1}, откуда
L_{n+1} >= 2 L_n - \sum_{k>=5} L_{n+1-k}
>= 2 L_n - \sum_{k>=5} L_n /c^{k-1} =
(2- \sum_{r>=4} c^{-r} ) L_n
Значит, для доказательства остаётся найти такое c на отрезке от 1 до 2, что
Если такое есть — всё доказано
Очень естественно такое искать, заменив конечную сумму (до r=29) на бесконечную (что соответствует тому, что запреты Кощея не останавливаются на 30 нотах)
Понятно, что неравенство станет сильнее, поэтому то c, которое ему будет удовлетворять, подойдёт и для исходного
Дальше — есть несколько путей
Можно просто угадать, что для золотого сечения
с=φ=(1+\sqrt{5})/2
неравенство обращается в равенство
Потому что сумма убывающей геометрической прогрессии со знаменателем 1/φ, начинающейся с 1, равна
1/(1- 1/φ) = 1/ (1/φ^2) = φ^2;
значит, в левой части получается
2- φ^{-4} * φ^2= 2- 1/φ^2 = 2 - (1-1/φ) = 1+ 1/φ = φ
Второй путь — можно сказать, что сумма геометрической прогрессии равна
c^{-4} / (1-c^{-1}) = c^{-3} / (c-1);
так что мы ищем такое c, для которого
Если привести к общему знаменателю и перенести c в левую часть — получается полиномиальное неравенство
Опять же, можно ещё раз увидеть, что на золотом сечении неравенство обращается в равенство ( 2-φ = 1/φ^2, φ-1 = 1/φ ), но можно и заметить, что какое-нибудь конкретное c этому неравенству удовлетворяет
И таких c есть целый интервал от золотого сечения φ=1.618… до чуть больше, чем 1.75
Достаточно проверить неравенство для любого из них
Наконец, где золотое сечение — там и последовательность Фибоначчи
И отсюда и вариант решения, когда вместо чистого геометрического роста доказывается неравенство L_{n+1} >= L_n + L_{n-1}