retagged by
6,529 views
3 votes
3 votes

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
retagged by

2 Answers

3 votes
3 votes

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

2 votes
2 votes

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)

Related questions

1 votes
1 votes
1 answer
2
radha gogia asked Mar 6, 2016
2,080 views
why do we count here empty string also , it has no 1's , so what's the reason for counting this ?
1 votes
1 votes
3 answers
3
Sanjay Sharma asked Mar 9, 2017
2,727 views
what is the probability that a randomly chosen bit string of length 10 is palindromea)1/64 b)1/32 c) 1/8 d)1/4
0 votes
0 votes
1 answer
4
Sanjay Sharma asked Mar 9, 2017
1,606 views
How many bit strings of length n contains 1)at least 2) at most 3) exactly r 1's