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$.
Problem
Source:
Tags: CSMC, CSMC 2018
ZetianLi
05.12.2018 11:13
I think (a) is AABA BBAB CABA CBAB ABAA BABB ABAC BABC ABBA BAAB ABAB BABA
NikoIsLife
07.12.2018 14:35
Let $f(n)$ be the number of strings of length $n$ from the set $\{A,B,C\}$ in which $CC$ occurs.
The number of strings of length $f(n)$ in which $CC$ does not occur is $3^n-f(n)$.
Therefore, $f(n)$ is defined by the recurrence relation:
$$f(n+1)=3f(n)+2(3^{n-2}-f(n-2))$$And we also have the starting values $f(0)=0,f(1)=0,f(2)=1$.
This gives us:
\begin{align*}f(0)&=0\\f(1)&=0\\f(2)&=1\\f(3)&=5\\f(4)&=21\\f(5)&=79\\f(6)&=281\\f(7)&=\boxed{963}\end{align*}
ZetianLi
07.12.2018 21:33
NikoIsLife wrote:
Let $f(n)$ be the number of strings of length $n$ from the set $\{A,B,C\}$ in which $CC$ occurs.
The number of strings of length $f(n)$ in which $CC$ does not occur is $3^n-f(n)$.
Therefore, $f(n)$ is defined by the recurrence relation:
$$f(n+1)=3f(n)+2(3^{n-2}-f(n-2))$$And we also have the starting values $f(0)=0,f(1)=0,f(2)=1$.
This gives us:
\begin{align*}f(0)&=0\\f(1)&=0\\f(2)&=1\\f(3)&=5\\f(4)&=21\\f(5)&=79\\f(6)&=281\\f(7)&=\boxed{963}\end{align*}
I got 1458, I think I forgot to subtract the overlap situations XD
ZetianLi
07.12.2018 21:35
NikoIsLife wrote:
Let $f(n)$ be the number of strings of length $n$ from the set $\{A,B,C\}$ in which $CC$ occurs.
The number of strings of length $f(n)$ in which $CC$ does not occur is $3^n-f(n)$.
Therefore, $f(n)$ is defined by the recurrence relation:
$$f(n+1)=3f(n)+2(3^{n-2}-f(n-2))$$And we also have the starting values $f(0)=0,f(1)=0,f(2)=1$.
This gives us:
\begin{align*}f(0)&=0\\f(1)&=0\\f(2)&=1\\f(3)&=5\\f(4)&=21\\f(5)&=79\\f(6)&=281\\f(7)&=\boxed{963}\end{align*}
I think I may lose 1 or 2 points in (b) XD rip