Question: 2018 Winter Final - 12
A string $s_1s_2{\dots}s_n$ is called a palindrome, if
$$
s_1s_2{\dots}s_{n-1}s_n = s_ns_{n-1}{\dots}s_2s_1,
$$
i.e., reading the string from left to right gives the
same result as reading the string from right to left.
Let $n \geq 3$ be an odd integer. You are given a string of length $n$, in which each character is a uniformly random element of $\{a,b,c\}$. The characters are independent of each other. What is the probability that this string is a palindrome?
Let $n \geq 3$ be an odd integer. You are given a string of length $n$, in which each character is a uniformly random element of $\{a,b,c\}$. The characters are independent of each other. What is the probability that this string is a palindrome?
(a)
$(1/2)^{(n-1)/2}$
(b)
$(1/2)^{(n+1)/2}$
(c)
$(1/3)^{(n-1)/2}$
(d)
$(1/3)^{(n+1)/2}$