Строки без повторяющихся подстрок

[Sonic86]

Придумал легкую задачу, возможно она подойдет для школьников. Постю только потому, что хочу узнать, баян или нет.

Пусть $x$ - строка в каком-то конечном алфавите.
Назовем строку $x$ сложной, если в ней есть несколько вхождений одинаковых неперекрывающихся подстрок длины $>1$ (например, подстрока $ab$ в $ababa$), иначе назовем строку $x$ простой.
Какова максимальная длина простой строки в алфавите из $k$ символов?

[Yadryara]

Sonic86 в сообщении #1178533 писал(а):

Какова максимальная длина простой строки в алфавите из $k$ символов?

$k^2+k+1$

Например, вариант максимальной строки для $k=4$:

$aaabbbcccdddacbdbadca$

[whitefox]

Sonic86 в сообщении #1178533 писал(а):

Какова максимальная длина простой строки в алфавите из $k$ символов?

Рассмотрим произвольную простую строку. Пусть первая и последняя буквы разные, тогда каждая из $k$ букв входит в эту строку не более чем $k+1$ раз, то есть длина такой строки не превышает $k^2+k.$ Если же первая и последняя буквы совпадают, то эта буква входит в строку не более чем $k+2$ раза, а остальные не более чем $k+1$ раз, то есть длина такой строки не превышает $k^2+k+1.$ Из чего следует, что

$$l_k \leqslant k^2+k+1$$

Возьмём простую строку $\alpha$ в алфавите $A$ из $k$ букв максимальной длины. Пусть буква $z$ не входит в алфавит, а слово заканчивается, например, буквой $a.$ Тогда можно построить простое слово в алфавите $A\cup \{z\}$ из $k+1$ букв длиной $l_k+2(k+1),$ например

$$\alpha zzzbzczd\dots za$$

То есть $l_k+2(k+1)\leqslant l_{k+1}.$ А так как $l_1=3,$ то

$$k^2+k+1\leqslant l_k$$

Следовательно

$$l_k=k^2+k+1$$