3 votes 3 votes How many 7 length bit strings have atleast 3 consecutive ones? Combinatory combinatory engineering-mathematics discrete-mathematic + – Balaji Jegan asked Jan 22, 2018 Balaji Jegan 1.2k views answer comment Share Follow See all 28 Comments See all 28 28 Comments reply gauravkc commented Jan 22, 2018 reply Follow Share Assuming it's binary Is it 80? 0 votes 0 votes Balaji Jegan commented Jan 22, 2018 reply Follow Share It's binary only. can u post your approach? 0 votes 0 votes Mk Utkarsh commented Jan 22, 2018 reply Follow Share gauravk you are over-counting 0 votes 0 votes gauravkc commented Jan 22, 2018 reply Follow Share Please point out Mk Utkarsh Since they have to be consecutive, I grouped them. Now we have that group 111 and rest 4 places that can have 0 or 1 0 or 1 at 4 places can be placed in 24 = 16 ways. The group can be placed at 5 places around those 4 bits here _ here _ here _ here _ here So 16 x 5 = 80 0 votes 0 votes Mk Utkarsh commented Jan 22, 2018 i edited by Mk Utkarsh Jan 22, 2018 reply Follow Share is it 40? or 41 0 votes 0 votes Mk Utkarsh commented Jan 22, 2018 reply Follow Share try placing 111 group in the beginning and then in the end by both the permutations you can get 1111111 0 votes 0 votes gauravkc commented Jan 22, 2018 reply Follow Share Oh yes :/ 1111111 is counted 5 times What approach did you use? 0 votes 0 votes Mk Utkarsh commented Jan 22, 2018 reply Follow Share yeah there are many multiple counts my approach is that we can shift 111 and still create unique numbers by placing 0 at immediate left from 1111 like 111xxxx - 16 ways 0111xxx - 8 ways x0111xx - 8 ways xx0111x - 8 ways 0000111 - 1 way but is that correct? 41 1 votes 1 votes Balaji Jegan commented Jan 22, 2018 reply Follow Share Notice the word "atleast" 0 votes 0 votes gauravkc commented Jan 22, 2018 reply Follow Share Similar qn here with same approach as Mk Utkarsh http://www.techtud.com/doubt/how-many-bit-string-length-eight-contain-either-three-consecutive-0s-or-four-consecutive-1s 0 votes 0 votes Balaji Jegan commented Jan 22, 2018 reply Follow Share There can be 3 consecutive 1s or 4 consecutive 1s or 5 consecutive 1s or 6 consecutive ones or all ones. My approach was to subtract all outlier cases from 128 0 votes 0 votes Balaji Jegan commented Jan 22, 2018 reply Follow Share 41 ain't the answer 0 votes 0 votes Mk Utkarsh commented Jan 22, 2018 reply Follow Share what is the answer? 0 votes 0 votes Mk Utkarsh commented Jan 22, 2018 reply Follow Share why do you think i am not considering atleast out of 41 strings in my solution every permutation contain atleast 3 and atmost 7 1's 1 votes 1 votes Balaji Jegan commented Jan 22, 2018 reply Follow Share These are the options given: 16 48 96 I think answer must be 48 as it lies closer to ur answer 0 votes 0 votes gauravkc commented Jan 22, 2018 reply Follow Share No explanation for solution? 1 votes 1 votes Ashwin Kulkarni commented Jan 22, 2018 reply Follow Share Mk Utkarsh's solution seems correct! I'm unable to find those 7 missing cases to make it 48. :( 1 votes 1 votes Balaji Jegan commented Jan 23, 2018 reply Follow Share Actually, I framed the question myself. I saw another question similar to this and created a new question. 0 votes 0 votes Balaji Jegan commented Jan 23, 2018 reply Follow Share This is the original question 0 votes 0 votes Balaji Jegan commented Jan 23, 2018 reply Follow Share @Mk Utkarsh, the answer to this question according to u will be 41/128, which does not match with any option. However if it was 48, then 48/128 = 3/8 0 votes 0 votes Manu Thakur commented Jan 23, 2018 reply Follow Share $\frac{47}{128} $ should be the probability. 1. $111XXXX = 2^4 = 16$ combinations 2. $X111XXX$ first X will be 0 and last 3 X can be $2^3 = 8$ ways. 3. $XX111XX$ first x = 2 ways, 2nd x will be 0, and last two $X = 2^2$ ways, total = $2*4 = 8$ ways 4. $XXX111X$ 3rd X has to be 0, rest three X $2^3=8$ ways 5. $XXXX111$ 4th X has to be 0, and rest three X $2^3=8 - 1 =7$ ways we need to deduct already counted 1 string that is, 1110111, it was already counted in case 1. Total Computed strings = $47$ Total bit strings with 7 bits = $2^7=128$ 3 votes 3 votes Mk Utkarsh commented Jan 23, 2018 reply Follow Share we need 1 more :p anyone up for that 0 votes 0 votes Mk Utkarsh commented Jan 23, 2018 reply Follow Share Balaji Jegan yeah i agree i was doing some mistake Manu found the right answer and maybe there can be one more combination we are unable to find 0 votes 0 votes Manu Thakur commented Jan 23, 2018 reply Follow Share there is no more combination i am 100% sure on that! May be the one who made this question in test didn't deduct the duplicate count. 1 votes 1 votes Mk Utkarsh commented Jan 23, 2018 reply Follow Share yeah probably 0 votes 0 votes Balaji Jegan commented Jan 23, 2018 reply Follow Share Yes the answer is 47/128. I CHECKED MANUALLY FOR ALL THE 128 CASES. 0 votes 0 votes sourav. commented Jan 23, 2018 reply Follow Share @manu is right . I have got another method to solve it. $\text{7 length bit strings have atleast 3 consecutive ones}=\text{7 length bit strings possible-no 3 consecutive 1}$ $\text{# of bit string of length n with no 3 consecutive 1}T(n)=T(n-1)+T(n-2)+T(n-3)$ $T(0)=1,T(1)=2,T(2)=4$ solving $T(7)=81$ so reqd answer=$2^{7}-81=128-81=47$ 4 votes 4 votes rajatmyname commented Mar 13, 2019 reply Follow Share Is this formula still valid if question asks for n length bit strings having 3 consecutive ones only? 0 votes 0 votes Please log in or register to add a comment.