XXI SILK ROAD MATHEMATICAL COMPETITION

Let the alphabet consist of letters $a_1,a_2,\dots ,a_{25}$. By a piece we always mean a piece of the strip containing exactly $17$ consecutive letters; different pieces may contain the same word. Say that a piece is singular if the word it contains is such.

We start with constructing an example containing $N=2\cdot 5^{17}$ singular words. Define a word $W=a_1{a}_2\dots a_{17}$; this will be the word having $k=5^{16}$ non-overlapping copies on the strip. There exist exactly $25^8=k$ possible $8$-letter sequences, consisting of letters $a_{18},a_{19},\dots ,a_{25}$; put them onto the strip in an arbitrary order, separating each two sequences by an instance of $W$. Each segment of the strip containing one $8$-sequence mentioned above (and no other letters) will be referred to as a part. Notice that the strip contains exactly $(8+17)k=5^{18}$ letters.

Clearly, the obtained strip contains $k$ non-overlapping copies of $W$. Now we show that any piece containing a whole part is singular — moreover, that the word it contains is met on no other piece. Since a part can be situated in a piece at $10$ different positions (starting from the $1$-st, from the $2$-nd, ..., or from the $10$-th letter of a piece), we will get that there are at least $10\cdot 5^{16}=N$ singular words.

Consider an arbitrary piece $p$ containing a word $P$. Either this piece contains a unique nonempty prefix which coincides with some suffix of $W$, or there is no such prefix — only in this case we will say that such prefix is empty. Let $b$ be the length of the defined prefix. Define similarly a suffix of $P$ which coincides with a prefix of $W$, and denote its length by $e$. Notice that the defined prefix and suffix do not overlap whenever $P\ne W$ (if $P=W$, we have $b=e=17$).

If the piece contains no whole part, then $\max \{b,e\}>9$. If the piece contains a part, then $b+e=9$ and $0\le b,e\le 9$. Thus, piece $p$ contains a part if and only if $\max \{b,e\}\le 9$, and in this case the position of the part at $P$ (and hence the position of $p$ at the strip) is uniquely determined. Therefore, in this case $P$ is met only on piece $p$, so this piece is singular. We have proven that the constructed example works.

It remains to prove that the number of singular words cannot exceed $N$. Enumerate the positions in the strip successively by $1,2,\dots ,5^{18}$ (the numeration is cyclic modulo $5^{18}$). Let $p_i$ denote the piece starting at position $i$, and let $P_i$ be the word on that piece. Let $n_1,\dots ,n_k$ be positions such that the pieces $p_{n_1},p_{n_2},\dots ,p_{n_k}$ are pairwise disjoint and contain the same word $W$ (from the problem statement). Clearly, those pieces are not singular.

For $i=1,2,\dots ,8$ and $1\le s\le k$, we say that a piece $p_{n_s+i}$ is a rank $i$ follower, while $p_{n_s-i}$ is a rank $i$ predecessor. All these pieces (followers and predecessors) are distinct; moreover, followers of a fixed rank are pairwise disjoint, and the same holds for predecessors. We will show that among $8\cdot 5^{16}$ followers of all ranks, at most $5^{16}$ pieces are singular (we will call this statement a quoted claim in the future); by symmetry, the same bound holds for predecessors. This will yield that there are at least $5^{16}+7\cdot 5^{16}+7\cdot 5^{16}=3\cdot 5^{17}$ non-singular pieces, which implies the desired bound.

Remark. We present a shorter (yet more ideological) proof of the quoted claim on the number of singular followers. Say that a singular follower's tail $T$ is minimal if none of its proper prefixes is a singular follower's tail. In particular, no minimal tail can be a proper prefix of other minimal tail.

For every minimal tail $T$ let us write down all $8$-letter sequences starting with $T$; if the length of $T$ is $d$, then the number of such sequences is $25^{8-d}$. No sequence could be written down twice; therefore, if there are $M$ minimal tails of lengths $d_1,\dots ,d_M$, then $$\sum _{i=1}^{M}25^{8-d_i}\le 25^8.$$ On the other hand, each singular follower's tail has a prefix which is a minimal tail. For a minimal tail $T$ of length $d$, there are at most $9-d$ singular followers whose tails start with $T$ — at most one per tail's length. Therefore, the number of singular followers does not exceed $$\sum _{i=1}^M(9-d_i)\le \sum _{i=1}^{M}25^{8-d_i}\le 25^8,$$ since $9-d\le 25^{8-d}$ for all $d=1,2,\dots ,8$.

Finally, if there is a singular follower $P_{n_s+8-m}$ whose tail is $U$, then such follower is unique. Therefore, all followers of larger ranks whose tails start with $U$ correspond to the same copy $p_{n_s}$ of $W$. Then the number of such followers (including $P_{n_s+8-m}$ itself) is at most $m+1\le 25^m$, as desired again. The claim, and the bound, are proven.