Solution: 2018 Winter Final - 12

Author: Michiel Smid

Question

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?

(a)

$(1/2)^{(n+1)/2}$

(b)

$(1/3)^{(n+1)/2}$

(c)

$(1/2)^{(n-1)/2}$

(d)

$(1/3)^{(n-1)/2}$

Solution

To guarantee that a string is a palindrome in this case, we have to ensure that the first half of the string matches the second half (but reversed).

At each position in the “half of the string”, there is a $\frac{1}{3}$ chance that the corresponding character in the other half of the string is the same since there are 3 character options (a, b, c) and only 1 of those can match.

Since the string is an odd integer, half of a string would be: $\frac{n-1}{2}$. So if $n = 3$, then half of the string would be $\frac{3-1}{2} = 1$. This makes sense, as we would check if the 1st and last character are the same, and the 2nd character we know would already be the same as itself.

This means that the total probability a string is a palindrome is: $( \frac{1}{3})^{n-1/2}$