Library / /46 of 68

, 2017

Combinatorics Difficulty 5.6 AIME, harder Prove it United States

Problem:

Sean is a biologist, and is looking at a string of length $66$ composed of the letters $A, T, C, G$ . A substring of a string is a contiguous sequence of letters in the string. For example, the string $A G T C$ has $10$ substrings: $A, G, T, C, A G, G T, T C, A G T, G T C, A G T C$ . What is the maximum number of distinct substrings of the string Sean is looking at?

Solution

Solution:

Let's consider the number of distinct substrings of length $\ell$ . On one hand, there are obviously at most $4^{\ell}$ distinct substrings. On the other hand, there are $67-\ell$ substrings of length $\ell$ in a length $66$ string. Therefore, the number of distinct substrings is at most
$\sum_{\ell=1}^{66} \min \left(4^{\ell}, 67-\ell\right) = 2100$
To show that this bound is achievable, one can do a construction using deBrujin sequences that we won't elaborate on here.

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 reproduced verbatim; metadata (topic, difficulty) added by this project.