In a language$,$ an alphabet with $25$ letters is used$;$ words are exactly all sequences of $($ not necessarily different $)$ letters of length $17.$ Two ends of a paper strip are glued so that the strip forms a ring$;$ the strip bears a sequence of $5^{18}$ letters$.$ Say that a word is singular if one can cut a piece bearing exactly that word from the strip$,$ but one cannot cut out two such non-overlapping pieces$.$ It is known that one can cut out $5^{16}$ non-overlapping pieces each containing the same word$.$ Determine the largest possible number of singular words$.$ (Bogdanov I.)
Problem
Source: SRMC 2022 P4
Tags: combinatorics
13.10.2022 17:03
I don't remember a combinatorics problem harder than this one... Answer: $2\times5^{17}.$ Official Solution: Let the alphabet of the letters $a_1,a_2,\cdots,a_{25}.$ By a piece we always mean a piece of the strip containing exactly $17$ consecutive letters; Different piece may contain the same word. Say that a piece is singular if the word it contain is such. We start with constructing an example containing $N= 2\times5^{17}$ singular words. Define a word $W=a_1,a_2,\cdots,a_{17};$ This will be the word having $k=5^{16}$ non-overlapping copies on the strip. There exist exactly $k=25^8$ possible $8-$letter sequences, consisting of letters $a_{18},a_{19},\cdots,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 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, \cdots, or from the $10-$th letter of a piece), we will get that there are at least $N=10\times 5^{16}$ singular words. Consider an arbitrary piece $p$ containing a a word $P.$ Either this piece contains a unique non empty 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\not =W$ (if $P=W,$ we have $b=c=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\le9.$ Thus, piece $p$ contains a part iff $max\{b,e\}\le9,$ 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 one 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,\cdots,5^{18}$ (the numeration is cyclic module $5^{18}$). Let $p_i$ denote the piece starting at positions $i,$ and let $P_i$ be the word on that piece. Let $n_1,\cdots,n_k$ be a positive such that the pieces $p_{n_1},p_{n_2},\cdots,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,\cdots,8$ and $1\le s \le k,$ we say that a piece $p_{n_{s+1}}$ is a rank $i$ follower, while $p_{n_{s-1}}$ 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\times 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 hold for predecessors. This will yield that there are at least $5^{16}+7 \times 5^{16}+7 \times 5^{16}=3\times 5^{17}$ non-singular pieces, which implies the desired bound. Thus, we are left to prove the claim quoted above. For any rank $i$ follower $p_{n_s+i}$ define its tail as its suffix of length $i$ (the tail consists of all letters which do not lie in $p_{n_s};$ We regard a tail as a sequence of letters). We show by induction on $m=0,1,\cdots,8$ that for every sequence $U$ consisting of $(8-m)$ letters, there are no more than $25^m$ followers whose tails contain $U$ as a prefix. The desired claim is obtained by setting $m=8.$ The base case $m=0$ is obvious; If a follower with tail $U$ is singular, then there is only one such follower. Let us perform the inductive step. If there is no singular follower whose tail is $U,$ then every singular follower's tail starting with $U$ starts in fact with some word of the form $U_{a_i}.$ For every $i=1,2,\cdots,25,$ there are at most $25^{m-1}$ such followers, by the inductive hypothesis. So the total number of such followers does not exceed $25\times 25^{m-1}=25^m,$ as desired. 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.