21-ші «Жібек жолы» математикалық олимпиадасы, 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}$.

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