Solution: 2017 Winter Final - 4

Author: Michiel Smid

Question

A bitstring $b_1b_2 \dots b_n$ is called a palindrome if $b_1b_2 \dots b_n = b_nb_{n-1} \dots b_1$, i.e., reading the string from left to right gives the same result as reading it from right to left. Let $n \geq 3$ be an odd integer. How many palindromes of length $n$ are there?

(a)

$2^{n-1}$

(b)

$2^{n-2}$

(c)

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

(d)

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

Solution

Let A be the event that a string of length n is a palindrome

The leftmost bit can be 1 or 0: 2 possibilities

The rightmost bit must be the same as the leftmost bit: 1 possibility

The second leftmost bit can be 1 or 0: 2 possibilities

The second rightmost bit must be the same as the second leftmost bit: 1 possibility

…

The innermost leftmost bit can be 1 or 0: 2 possibilities

The innermost rightmost bit must be the same as the innermost leftmost bit: 1 possibility

$ |A| = 2 \cdot 1 \cdot 2 \cdot 1 \cdot … \cdot 2 \cdot 1 = 2^{n/2} $

Usually, this would be right; however, we know the middle bit is always the same as itself AND n/2 is a \fraction since n is odd

$ |A| = 2^{ \frac{n+1}{2}} $