MathDB
Problems
Contests
National and Regional Contests
Canada Contests
Canadian Senior Mathematics Contest
2018 Canadian Senior Mathematics Contest
B3
B3
Part of
2018 Canadian Senior Mathematics Contest
Problems
(1)
CSMC 2018 Part B Problem 3
Source:
11/24/2018
A string of length
n
n
n
is a sequence of
n
n
n
characters from a specified set. For example,
B
C
A
A
B
BCAAB
BC
AA
B
is a string of length 5 with characters from the set
{
A
,
B
,
C
}
\{A,B,C\}
{
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
C
A
CA
C
A
is a substring of
B
C
A
A
B
BCAAB
BC
AA
B
but
B
A
BA
B
A
is not a substring of
B
C
A
A
B
BCAAB
BC
AA
B
. [*]List all strings of length 4 with characters from the set
{
A
,
B
,
C
}
\{A,B,C\}
{
A
,
B
,
C
}
in which both the strings
A
B
AB
A
B
and
B
A
BA
B
A
occur as substrings. (For example, the string
A
B
A
C
ABAC
A
B
A
C
should appear in your list.) [*]Determine the number of strings of length 7 with characters from the set
{
A
,
B
,
C
}
\{A,B,C\}
{
A
,
B
,
C
}
in which
C
C
CC
CC
occures as a substring. [*]Let
f
(
n
)
f(n)
f
(
n
)
be the number of strings of length
n
n
n
with characters from the set
{
A
,
B
,
C
}
\{A,B,C\}
{
A
,
B
,
C
}
such that [*]
C
C
CC
CC
occurs as a substring, and[*]if either
A
B
AB
A
B
or
B
A
BA
B
A
occurs as a substring then there is an occurrence of the substring
C
C
CC
CC
to its left. (for example, when
n
=
6
n\;=\;6
n
=
6
, the strings
C
C
A
A
B
C
CCAABC
CC
AA
BC
and
A
C
C
B
B
B
ACCBBB
A
CCBBB
and
C
C
A
B
C
C
CCABCC
CC
A
BCC
satisfy the requirements, but the strings
B
A
C
C
A
B
BACCAB
B
A
CC
A
B
and
A
C
B
B
A
B
ACBBAB
A
CBB
A
B
and
A
C
B
C
A
C
ACBCAC
A
CBC
A
C
do not). Prove that
f
(
2097
)
f(2097)
f
(
2097
)
is a multiple of
97
97
97
.
CSMC
CSMC 2018