XVII математическая олимпиада «Шелковый путь», 2022 год

В письменности используется 25-буквенный алфавит, а словами являются в точности все 17-буквенные последовательности. На полоске, склеенной в кольцо, написана последовательность из $5^{18}$ букв алфавита. Назовём слово уникальным, если из полоски можно вырезать участок, содержащий это слово, но нельзя вырезать два таких непересекающихся участка. Известно, что из полоски можно вырезать $5^{16}$ непересекающихся копий какого-то слова. Найдите наибольшее возможное количество уникальных слов. ( И. Богданов )

Комментарий/решение

Ответ: $2 \cdot 5^{17}$

Оценка: Назовем слово, которое повторяется $5^{16}$ раз копипастом. Рассмотрим буквенную последовательность из $8$ букв против часовой стрелки после каждого копипаста - пусть это будут последовательности $T_1, T_2, \ldots T_{5^{16}}$. Выделим в каждой из этих последовательностей первый кусок из $a_i$ ($1 \leq a_i \leq 8$) такой, что этот кусок не является первыми $a_i$ буквами какой то другой из $T_i$, при этом, если такого куска нет для какой то из $T_i$, то не выделяем ничего, назовем каждый такой кусок для последовательности $T_i$ - $X_i$. Рассматривать будем слова, которые образованы первыми $x$ ($1 \leq x \leq 8$) буквами в $T_i$ и $17-x$ буквами соответствующего копипаста, назовем $8$ таких слов $i$-словами. Сразу заметим, что все такие слова не пересекаются для различных $i$. Теперь мы можем ограничить снизу количество неуникальных слов из всех $i$-слов. Если для какого то $T_i$ не выписано $a_i$, то этот $T_i$ полностью повторяется каким то другим $T$, тогда любое из $8$ $i$-слов будет неуникальным. Рассмотрим любое из слов, которое образовано из $l\leq a_i-1$ первых букв последовательности $T_i$ и оставшихся, тогда мы знаем, что такой кусок есть в каком то другом $T$, пользуясь минимальностью $a_i$, и добавив оставшиеся одинаковые буквы из копипаста, получаем, что это слово не уникально, тогда всего будет хотя бы $\sum (a_i-1) + 8(5^{16}-t)$ неуникальных слов, где $t$ - количество выделенных $a$. Оценим сумму $a_i$. Для этого на каждом $T_i$ будем заменять последовательность, которая стоит на последних $8-a_i$ местах, наоборот всевозможными последовательностями, которых ровно $25^{8-a_i}$, тогда между разными $i$ никакие две не совпадут, потому что "хвосты" не совпадают, тогда $9t - \sum a_i = \sum (9-a_i) \leq \sum 25^{8-a_i} \leq 25^8$ (воспользовались очевидным $25^x \geq x+1$ для неотрицательного $x$, откуда $\sum (a_i-1) + 8(5^{16}-t) \geq 8 \cdot 5^{16} - 25^8 = 7 \cdot 5^{16}$, повторяя аналогично с последовательностями $T'$, которые образованы 8 буквами по часовой стрелке от копипастов, получим еще $7 \cdot 5^{16}$ неуникальных и добавим еще $5^{16}$ копипастов, тогда останется $2 \cdot 5^{17}$ слов, которые могут быть уникальными.

Пример: Для примера рассмотрим $5^{16}$ копий слова с различными буквами, расположенных на расстоянии $8$ друг от друга, а в промежутки между ними запишем $25^8$ различных слов, тогда несложно проверить, что уникальными будут являться в точности все слова, которые содержат полностью один из промежутков, то есть $10$ слов для $5^{16}$ промежутков, а всего $2 \cdot 5^{17}$

Альтернативное доказательство оценки:

Определим для каждого участка из 17 букв его середину - букву, находящуюся на 9-ой позиции слева. Также назовем участки, содержащие слово, встречающееся $5^{16}$ раз копипастами. Наконец, отметим все середины уникальных слов.

Замечаем, что в примере отмеченные буквы - это все буквы полоски не в копипастах, и по 2 буквы на концах каждого копипаста.

Лемма:

Количество отмеченных букв в копипастах не больше, чем 2 умножить на количество копипаст, то есть $2 \cdot 5^{16}$.

Доказательство:

Пусть $x_1, x_2,\ldots, x_{17}$ - количества отмеченных букв на позициях $1, 2, \ldots, 17$ всех копипаст соответственно.

Надо доказать, что $x_{10}+x_{11}+\ldots+x_{17} \leq 5^{16}$, потому что для первых 8 $x$ аналогичное доказательство, и $x_9$ очевидно $0$.

Зафиксируем какой-то $x_{9+i}$ для $(1 \leq i \leq 7)$ и ограничим $x_{17}$. Слово с серединой $9+i$ какого-то копипаста будет содержать $17-i$ последних букв копипаста и $i$ букв после копипаста. Значит после копипастов $x_{9+i}$ уникальных наборов из $i$ букв, и $x_{17}$ будет равно количеству уникальных 8-буквенных наборов после копипаста. Количество уникальных наборов из 8, содержащих уникальный префикс из $i$ будет не больше $x_{9+i}$, а количество не содержащих - не больше $(25^i-x_{9+i}) \cdot 25^{8-i}$. Тогда $x_{17} \leq x_{9+i}+25^{8-i}(25^i-x_{9+i})=25^8-x_{9+i}(25^{8-i}-1)$, что равносильно $\boxed{x_{9+i} \leq \dfrac{25^8-x_{17}}{25^{8-i}-1}}$.

Получаем, что $x_{10}+x_{11}+\ldots+x_{17} \leq \sum\limits_{i=1}^{7} \frac{25^8-x_{17}}{25^{8-i}-1}+x_{17}=(25^8-x_{17})\left(\sum\limits_{i=1}^{7} \frac{1}{25^{8-i}-1} \right)+x_{17} \leq 25^8=5^{16}$. Последнее неравенство вышло из того, что $x_{17} \leq 25^8$ и $\sum\limits_{i=1}^{7} \frac{1}{25^{8-i}-1} < 7 \cdot \frac{1}{24} < 1$.

Отсюда сразу выходит требуемая оценка, потому что количество букв полоски не в копипастах $8 \cdot 5^{16}$, значит общее количество отмеченных букв (равное количеству уникальных слов) не больше $2 \cdot 5^{16}+8 \cdot 5^{16}=2 \cdot 5^{17}$.

Ема базару нет тема тема