Problem

Source:

Tags: CSMC, CSMC 2018



A string of length $n$ is a sequence of $n$ characters from a specified set. For example, $BCAAB$ is a string of length 5 with characters from the set $\{A,B,C\}$. A substring of a given string is a string of characters that occur consecutively and in order in the given string. For example, the string $CA$ is a substring of $BCAAB$ but $BA$ is not a substring of $BCAAB$. List all strings of length 4 with characters from the set $\{A,B,C\}$ in which both the strings $AB$ and $BA$ occur as substrings. (For example, the string $ABAC$ should appear in your list.) Determine the number of strings of length 7 with characters from the set $\{A,B,C\}$ in which $CC$ occures as a substring. Let $f(n)$ be the number of strings of length $n$ with characters from the set $\{A,B,C\}$ such that $CC$ occurs as a substring, and if either $AB$ or $BA$ occurs as a substring then there is an occurrence of the substring $CC$ to its left. (for example, when $n\;=\;6$, the strings $CCAABC$ and $ACCBBB$ and $CCABCC$ satisfy the requirements, but the strings $BACCAB$ and $ACBBAB$ and $ACBCAC$ do not). Prove that $f(2097)$ is a multiple of $97$.