195 views

A palindrome is a string whose reversal is identical to the string. How many bit strings of length n are palindromes?

1.   2⌈n⁄2⌉
2.   2(⌊ n/2⌋ )
3.   2⌈n⁄2⌉ -1
4.   2(⌊ n/2⌋) -1

Try with N= 2 you get aa,bb 2⌈n⁄2⌉  = 2

Try with N= 3 you get aaa,bbb ,aba , bab  2⌈n⁄2⌉  = 4

Try with N= 4 you get aaaa,bbbb ,abba , baab , 2⌈n⁄2⌉  = 4

The trick here is to realize that a palindrome of length n is completely determined by its first ceiling(n/2)  bits.
This is true because once these bits are specified, the remaining bits, read from right to left, must be identical
to the first floor(n/2) bits, read from left to right. Furthermore, these first ceiling(n/2) bits can be specified at will,
and by the product rule, there are 2^ceiling(n/2) ways to do so. Hence answer is 2^ceiling(n/2)--> Option (A)