Кощей придумал для Ивана-дурака испытание. Он дал Ивану волшебную дудочку, на которой можно играть только две ноты — до и си. Для прохождения испытания Ивану нужно сыграть какую-нибудь мелодию из 300 нот на свой выбор. Но до того, как он начнёт играть, Кощей выбирает и объявляет запретными одну мелодию из пяти нот, одну — из шести нот, …, одну — из 30 нот. Если в какой-то момент последние сыгранные ноты образуют одну из запретных мелодий, дудочка перестаёт звучать. Сможет ли Иван пройти испытание, какие бы мелодии Кощей ни объявил запретными?
Понятно, что вместо мелодий можно говорить про слова из двух символов — например (чтобы не говорить « до » и « си »), из 0 и 1.
Для начала — а что, если Кощей начинает запрещать не с длины 5, а с длины 3? Оказывается, что тогда он может выиграть!
Действительно: пусть он сначала запретит слово 001. Тогда за двумя нулями может идти только третий — и значит, только последовательность из одних нулей. Так что пара запретов 001 + 000000000000 практически равносильна запрету просто на два нуля. (Практически — потому что если мы говорим о словах конечной длины, то там незадолго до конца написать короткий хвост из нулей будет можно, но 300 это достаточно большая длина, чтобы всё закончилось до того.)
Пусть Кощей эти два запрета (001 + 000000000000) и наложит.
Итак, два нуля запрещены, значит, за каждым нулём следует единица. Отлично!
Теперь Кощей запрещает 1101. Поскольку за нулём должна следовать единица — это более-менее то же самое, что запретить просто 110. И поэтому за двумя единицами будет следовать третья — так что, добавив к этому запрету 1111111111, Кощей добивается того, что и две единицы подряд запрещены.
За 0 следует 1, за 1 следует 0, теперь Кощей запрещает 01010 — и испытание становится непроходимым.
(Кстати, последовательности из 0 и 1 выше можно сократить до длин 6 и 7 соответственно — там они длинные, чтобы показать, что в этом месте можно обойтись и очень длинным запретом.)