Math, asked by Drishit8890, 11 months ago

How many bit strings of length 10 contain either five consecutive 0s or five consecutive 1s?

Answers

Answered by Gardenheart65
0

The problem with your approach is that you are counting some arrangements more than once. Eg when you count by grouping and summing, you must take care that the groups are exclusive. For example, you count:

00000***** →25→25

*00000**** →25→25

but a configuration like 0000001111 belongs to both groups, hence you are couting it twice. And some, more than twice (eg, 0000000111 belongs to three groups).

To count the strings of 10 bits with at least 5 consecutive zeros, lets group them according to k=k= the first zero position in the (possibly larger than 5) run. Then k∈{1,2,3,4,5,6}k∈{1,2,3,4,5,6} (counting from one).

For k=1k=1, we have 2525 strings: ( 00000*****)

For k>1k>1 , we have 2424 strings (eg *100000***for k=3k=3)

This groping is exhaustive and exclusive. Hence the number of strings with at least 5 consecutive zeros is 25+5×24=11225+5×24=112

By symmetry, the number of strings with at least 5 consecutive ones is the same; however, this would count both 0000011111 and 1111100000twice (as you noticed), hence the total number is

112+112−2=222112+112−2=222

Notice that this method only works only because ℓ≥n/2ℓ≥n/2 (ℓℓ is the runlength, nn the total length) , otherwise more complicated methods would be needed (example).

Similar questions