Maths Olympiad Prep

Library / /4 of 4

Combinatorics Difficulty 7.7 National olympiad, round 2 Prove it Silk Road Mathematics Competition

In a language, an alphabet with 25 letters is used; words are exactly all sequences of (not necessarily different) letters of length 1717. Two ends of a paper strip are glued so that the strip forms a ring; the strip bears a sequence of 5185^{18} letters. Say that a word is singular if one can cut out 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 5165^{16} non-overlapping pieces each containing the same word. Determine the largest possible number of singular words. (Bogdanov I.)

Solution

Let the alphabet consist of letters a1,a2,,a25a_1, a_2, \dots, a_{25}. By a piece we always mean a piece of the strip containing exactly 1717 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=2517N = 2 \cdot 5^{17} singular words. Define a word W=a1a2a17W = a_1a_2 \dots a_{17}; this will be the word having k=516k = 5^{16} non-overlapping copies on the strip. There exist exactly 258=k25^8 = k possible 88-letter sequences, consisting of letters a18,a19,,a25a_{18}, a_{19}, \dots, a_{25}; put them onto the strip in an arbitrary order, separating each two sequences by an instance of WW. Each segment of the strip containing one 88-sequence mentioned above (and no other letters) will be referred to as a part. Notice that the strip contains exactly (8+17)k=518(8+17)k = 5^{18} letters.

Clearly, the obtained strip contains kk non-overlapping copies of WW. 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 1010 different positions (starting from the 11-st, from the 22-nd, ..., or from the 1010-th letter of a piece), we will get that there are at least 10516=N10 \cdot 5^{16} = N singular words.

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

If the piece contains no whole part, then max{b,e}>9\max\{b, e\} > 9. If the piece contains a part, then b+e=9b + e = 9 and 0b,e90 \le b, e \le 9. Thus, piece pp contains a part if and only if max{b,e}9\max\{b, e\} \le 9, and in this case the position of the part at PP (and hence the position of pp at the strip) is uniquely determined. Therefore, in this case PP is met only on piece pp, 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 NN. Enumerate the positions in the strip successively by 1,2,,5181, 2, \dots, 5^{18} (the numeration is cyclic modulo 5185^{18}). Let pip_i denote the piece starting at position ii, and let PiP_i be the word on that piece. Let n1,,nkn_1, \dots, n_k be positions such that the pieces pn1,pn2,,pnkp_{n_1}, p_{n_2}, \dots, p_{n_k} are pairwise disjoint and contain the same word WW (from the problem statement). Clearly, those pieces are not singular.

For i=1,2,,8i = 1, 2, \dots, 8 and 1sk1 \le s \le k, we say that a piece pns+ip_{n_s+i} is a *rank ii follower*, while pnsip_{n_s-i} is a *rank ii 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 85168 \cdot 5^{16} followers of all ranks, at most 5165^{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 516+7516+7516=35175^{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 TT 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 TT let us write down all 88-letter sequences starting with TT; if the length of TT is dd, then the number of such sequences is 258d25^{8-d}. No sequence could be written down twice; therefore, if there are MM minimal tails of lengths d1,,dMd_1, \dots, d_M, then
i=1M258di258. \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 TT of length dd, there are at most 9d9-d singular followers whose tails start with TT — at most one per tail's length. Therefore, the number of singular followers does not exceed
i=1M(9di)i=1M258di258, \sum_{i=1}^{M} (9 - d_i) \le \sum_{i=1}^{M} 25^{8-d_i} \le 25^8,
since 9d258d9 - d \le 25^{8-d} for all d=1,2,,8d = 1, 2, \dots, 8.

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

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.