First time here? Checkout the FAQ!
+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
asked in Combinatory by Veteran (13.4k points)  
retagged by | 293 views

2 Answers

+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

answered by Veteran (49.3k points)  
0 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)

answered by (369 points)  
for even length its right

but for odd length N=3 how come ur getting 4??

considering can only be two ways

that is position of a can be in two places

so for odd it should be floor(n/2) right??

please correct me

Related questions

Top Users Sep 2017
  1. Habibkhan

    8312 Points

  2. Warrior

    2862 Points

  3. rishu_darkshadow

    2796 Points

  4. Arjun

    2766 Points

  5. A_i_$_h

    2526 Points

  6. manu00x

    2094 Points

  7. nikunj

    1980 Points

  8. Bikram

    1874 Points

  9. makhdoom ghaya

    1810 Points

  10. SiddharthMahapatra

    1718 Points

26,283 questions
33,842 answers
31,193 users