|
|
 |
Условие
Кощей придумал для Ивана-дурака испытание. Он дал Ивану волшебную дудочку, на которой можно играть только две ноты – до и си. Для прохождения испытания Ивану нужно сыграть какую-нибудь мелодию из 300 нот на свой выбор. Но до того, как он начнёт играть, Кощей выбирает и объявляет запретными одну мелодию из пяти нот, одну – из шести нот, ..., одну – из 30 нот. Если в какой-то момент последние сыгранные ноты образуют одну из запретных мелодий, дудочка перестаёт звучать. Сможет ли Иван пройти испытание, какие бы мелодии Кощей ни объявил запретными?Решение 1
Рассмотрим всевозможные мелодии из двух нот длины $p$ = 13; их 213 штук. Каждую из этих мелодий можно продолжить периодически в обе стороны, получая бесконечные периодические мелодии; скажем, что две такие мелодии эквивалентны, если одна из них получается из другой сдвигом. С точностью до такой эквивалентности, есть (213 – 2):13 + 2 = 632 разных периодических последовательности.Посмотрим, сколько из них содержат запретные мелодии. Поскольку мы разрешаем сдвиг – можно считать, что запретная мелодия начинается с фиксированного (например, первого) места. Поэтому из-за запретных мелодий длины $k$ = 5, 6, ..., 12 мы вычеркнем не больше 28, 27, ..., 21 периодических последовательностей из нашего списка, а из-за последовательностей длины $k$ = 13, ..., 30 – не более одной. Итого запреты Кощея вычёркивают не больше (29 –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 > 35 и 7³·1·3 > 45.
Замечания
Несложно увидеть, что если бы длины запретных мелодий начинались с 3 нот, а не с 5, то Кощей мог бы не дать Ивану победить. Действительно, обозначим ноту до через 0 и си через 1; запрет на мелодию 001 приводит к тому, что сыграв два раза подряд 0, Иван вынужден будет играть только его. Вкупе с запретом на 0000000000 – это запретит просто $00$ везде, кроме самого конца мелодии, и потому за каждым 0 Ивану придётся сразу играть 1. Добавив к этому 1101 и 11111111, Кощей точно так же обеспечивает, чтобы за 1 Иван вынужден был бы играть 0. И наконец, добавив 010101, Кощей обеспечивает себе победу.Более того, существует и пример набора запретов, приводящий к победе Кощея и начинающийся с запрета длины 4: он был приведён в замечании 2.3 в работе Two notes on subshifts (Proc. Amer. Math. Soc. 2012. V. 140, no. 2. P. 1617--1622.) Дж. С. Миллера: $$ 1000, 10011, 100101, 1011111, 10111101, 101110101,$$ $$ 1011101101, 10110101101, 101101010101, 1011010101101,$$ $$0^{m_1}, 1^{m_2}, (100)^{m_3}, (1110)^{m_4}, (110)^{m_5}, (10)^{m_6},$$ где $m_j$ достаточно большие, а степень означает повторение.
Последовательности, не содержащие какого-либо заданного набора запрещённых участков, исследовались в различных ситуациях в математике на протяжении более ста лет. Так, в 1906 году норвежский математик Аксель Туэ (A. Thue. Über unendliche Zeichenreihen; перевод на английский см. J. Berstel, Axel Thue's papers on repetitions in words: a translation) показал, что существует последовательность из 0 и 1, в которой ни один её участок не повторяется три раза подряд – иными словами, существует последовательность с запретами вида 000, 111, 010101, 101010 и так далее. Эта последовательность сейчас называется последовательностью Туэ–Морса; её можно определить, например, как последовательность сумм по модулю 2 цифр двоичной записи числа $n& =0, 1, 2, 3, ...: $$ 0,1,1,0,1,0,0,1,\dots; $$ её также можно строить рекуррентно, начиная с одного символа 0 и последовательно дописывая после записанной строки её же с заменой 0 на 1 и 1 на 0.
Им же была построена последовательность из трёх символов, 0, 1 и 2, в которой ни одно слово не повторяется два раза подряд – иными словами, запрещены подслова вида 00, 2121, 0202 и так далее.
Не зная об этом, в 1937 году последовательности из трёх символов без повторяющихся подряд подслов и из двух символов без подслов, повторяющихся подряд трижды, построил С.Е. Аршон (см. Доказательство существования $n$-значных бесконечных асимметричных последовательностей).
В 1974-75 годах последовательности с запретами обсуждались в «Кванте». В задаче М300* рассматривалась последовательность в алфавите из трёх символов, избегающая запрещённых подслов, все из которых имеют разную длину. В задаче М310 требовалось доказать, что среди $n$-значных чисел есть по меньшей мере $8^n$, в которых никакая последовательность цифр не повторяется подряд два раза. Их решениям были посвящены статьи Г. Гуревича Бесповторные последовательности и А. Степина и А. Таги-Заде Слова с ограничениями.
Такие вопросы интересны не только сами по себе, но и в связи с задачами алгебры – когда рассматриваются длинные произведения образующих (как раз оказывающиеся словами в конечном алфавите), а наличие запрещённого подслова позволило бы упростить такое произведение. См., например, работу Е.С. Голода и И.Р. Шафаревича О башне полей классов. На лемму 3 этой работы можно смотреть как на достаточное условие наличия сколь угодно длинных слов в алфавите из $d$ символов, избегающих списка запрещённых слов, в котором $r_i$ слов длины $i$ = 2, 3, ...; это условие формулируется в терминах неотрицательности коэффициентов некоторого степенного ряда.
Очень естественное построение одной бесконечной мелодии, избегающей данных запретов, описано в уже цитировавшейся выше работе Дж. С. Миллера «Two notes on subshifts». Оно основано на «отслеживании» уже почти сыгранных запрещённых мелодий, и достаточное условие, позволяющее этому построению работать, очень близко к уже обсуждавшемуся здесь. А именно, предложение 2.1 этой работы утверждает, что достаточно, чтобы нашлось $c$ > 1, для которого $$ d - \sum\limits_{k=2}^{\infty} r_k c^{-(k-1)} \ge c,$$ где $d$ – число возможных нот, а $r_k$ – число запретных мелодий длины $k$. Это же условие применяется в недавнем препринте М. Розенфельда Finding lower bounds on the growth and entropy of subshifts over countable groups для экспоненциальной оценки роста количества разрешённых слов и энтропии отображения сдвига, действующего на них. Заключение леммы 3 этого препринта утверждает, что тогда $L_{n+1}\ge c L_n$, и рассуждение проходит по уже знакомой читателю схеме. Работы Миллера и Розенфельда и послужили первоисточником данной задачи.
Последовательности с запретами исследуются и в теории динамических систем – из совсем недавних работ можно упомянуть, например, работу Р. Павлова On subshifts with slow forbidden word growth.
Возвращаясь к бесповторным последовательностям, упомянем одну открытую задачу в этой области (спасибо А. Куликову за ссылку). Последовательность Туэ из трёх символов 0, 1, 2 не содержит повторяющихся подряд подслов. А что, если мы должны построить последовательность без повторяющихся подряд подслов, в которой для каждого места есть выбор из трёх символов – но наборы разрешённых символов разные для разных мест? Казалось бы, это должно быть только проще (если наборы символов разные, то совпадений может быть меньше) – но даже для случая, когда для каждого места есть выбор из четырёх символов, это было доказано лишь недавно (J. Grytczuk, J. Kozik, P. Micek, New approach to nonrepetitive sequences)}.
Более того, в качестве (удивительной) иллюстрации сложности данного вопроса можно привести пример модификации задачи о четырёх красках. А именно, допустим, что для карты на плоскости для каждой страны есть свой набор из $k$ цветов и картограф хочет раскрасить каждую страну в один из соответствующих цветов так, чтобы соседние страны были раскрашены в разные цвета. Хотя кажется, что от того, что цвета могут быть разными, получение раскраски должно только упроститься – оказывается, что при $k$ = 4 есть контрпример: (очень понятно устроенная) карта, которую раскрасить требуемым образом нельзя! Существование такого примера было сформулировано как гипотеза в работе Эрдеша, Рубина и Тэйлора Choosability in graphs, а сам этот такой пример был построен в работе 1993 года М. Войт List colourings of planar graphs. А гипотеза о том, что $k$ = 5 цветов всегда достаточно (сформулированная в той же работе Эрдеша, Рубина и Тэйлора), была доказана в работе 1994 года К. Томассена Every Planar Graph Is 5-Choosable.
