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)
3578 Points
2314 Points
1950 Points
1852 Points
1682 Points
1296 Points
1282 Points
1122 Points
1072 Points
1028 Points
246 Points
202 Points
108 Points
94 Points
90 Points
Gatecse