A palindrome is a string whose reversal is identical to the string. How many bit strings of length n are palindromes?
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
A is answer
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)
3946 Points
2464 Points
1842 Points
1650 Points
1268 Points
1184 Points
1100 Points
1052 Points
900 Points
692 Points
Gatecse
hi, but according to this post
Nice Post.Thanks,
Congratulations