Задача 67320

Темы:    [ Последовательности (прочее) ] [ Классическая комбинаторика (прочее) ] [ Подпоследовательности ]

Сложность: 5 Классы: 8,9,10,11

Условие

Автор: Клепцын В.А.

Кощей придумал для Ивана-дурака испытание. Он дал Ивану волшебную дудочку, на которой можно играть только две ноты  – до и си. Для прохождения испытания Ивану нужно сыграть какую-нибудь мелодию из 300 нот на свой выбор. Но до того, как он начнёт играть, Кощей выбирает и объявляет запретными одну мелодию из пяти нот, одну  – из шести нот, ..., одну  – из 30 нот. Если в какой-то момент последние сыгранные ноты образуют одну из запретных мелодий, дудочка перестаёт звучать. Сможет ли Иван пройти испытание, какие бы мелодии Кощей ни объявил запретными?

Решение 1

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

Решение 2

Для каждого $n$ зададимся вопросом: а сколько вообще мелодий длины $n$, не содержащих запретных, Иван может сыграть? Обозначим это количество через $L_n$ и для удобства положим $L_0=1$.

Оценим рост последовательности $L_n$. Сыграв после такой мелодии из $n$ нот каждую из двух возможных нот, мы получаем $2L_n$ мелодий длины $n+1$; при этом запретная мелодия в такой последовательности могла возникнуть только в конце (потому что мы предполагаем, что в первых $n$ нотах запретных мелодий нет). Если такая полученная мелодия оканчивается на запретную длины $k$, то после выкидывания этой запретной остаётся начальная часть из $n+1-k$ нот, не содержащая запретных мелодий,  – поэтому таких мелодий не больше $L_{n+1-k}$. Вычёркивая из исходных $2L_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\ge 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, \dots, 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^3 \cdot 1 \cdot 2 > 3^5$ и $7^3 \cdot 1 \cdot 3 > 4^5.$

Замечания

Несложно увидеть, что если бы длины запретных мелодий начинались с 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,\dots$: $$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,\dots$; это условие формулируется в терминах неотрицательности коэффициентов некоторого степенного ряда.

Очень естественное построение одной бесконечной мелодии, избегающей данных запретов, описано в уже цитировавшейся выше работе Дж. С. Миллера «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.

Источники и прецеденты использования

олимпиада
Название	Московская математическая олимпиада
год
Номер	87
Год	2024
класс
Класс	11
задача
Номер	6
олимпиада
Название	Турнир городов
год/номер
Дата	2023/24
Номер	45
вариант
Вариант	весенний тур, сложный вариант, 10-11 класс
задача
Номер	6