0
$\begingroup$

How many bit strings of length $20$ have either less than ten $1$’s or contain $11$ as a substring? The answer is $2^{20}-2$.

I am wondering how did they get $2$? Because if a string contains $11$ as a substring, then out of $20$ positions $2$ of them are fixed. Furthermore if the string has more than ten ones in it, then the solution to get those ten positions specifically will be $_{20}C_{10}$. (Note I am not taking the substring case into consideration here as of now.)

Hence the number of strings will be $2^{20}-\ _{20}C_{12}$. But the answer is $2^{20}-2$. Can someone give me a better explanation? Or is my chain of reasoning wrong?

$\endgroup$
4
  • 5
    $\begingroup$ Here's a better question : except for $010101010101010101,101010101010101010$ every other bit string of length $20$ would have this property. Knowing this, can you see why the answer comes? $\endgroup$
    – Sarvesh Ravichandran Iyer
    Jan 5, 2018 at 23:06
  • 1
    $\begingroup$ $2^{20}$ is the number of length-20 bitstrings. In the case that there are strictly more than $10$ 1's then there are eleven or more $1$'s, i.e. nine or fewer $0$'s. By pigeon-hole principle within the spaces to the left or right or inbetween each of those $0$'s (there are at most ten such spaces), there must be at least one space with two or more $1$'s in it (since $11>10$) which would cause a substring of $11$. We see then that every string with strictly less than ten $1$'s and every string with strictly more than ten $1$'s will satisfy one of our conditions... $\endgroup$
    – JMoravitz
    Jan 5, 2018 at 23:08
  • $\begingroup$ Hi Sparsh! Welcome to MSE! You will find that you will receive more, better answers if you take the time to format your questions using MathJax (much of the time you can just put your mathematical expressions in dollar signs (maybe with some curly braces): e.g. 2^20-2 could be written $2^{20}-2$ to be written as $2^{20}-2$. $\endgroup$
    – eepperly16
    Jan 5, 2018 at 23:54
  • $\begingroup$ Notice you are taking the NEGATION of " less than ten 1’s" but you are taking the POSITIVE of " contain 11 as a substring". Why are you doing that? Either calculate 'less that ten 1's' + 'has 11 as substring - ('less than ten 1s and 11 as subtring') and take the POSITIVES of bot with exclusion inclusion or calculate $2^{20} - $ (more than ten 1's and no 11's) and take the NEGATIVE of both. Hint: (more than ten 1's and no 11's) = 2. Just 2. $\endgroup$
    – fleablood
    Jan 6, 2018 at 0:25

1 Answer 1

Reset to default
2
$\begingroup$

This is a tricksy question.

Let P mean "has $11$ as substring" and Q mean "has less than 10 $1$s".

Then # of P or Q = #all - #NEITHER( P nor Q) = #all - #BOTH NOT P AND NOT Q.

#all = $2^{20}$.

NOT P means "never has $11$ as a substring" means "every one has a $0$ to either side of it".

NOT Q means has at least $10$ $1$.

NOT P AND NOT Q means that at least $10$ $1$s and every one has a $0$ to either so so at least $10$ $0$ but as there are at most $20$ bits there are $10$ $0$s and $10$ $1$ and all the $1$ have a $0$ between them.

So NOT P AND NOT Q means "either $10101010101010101010$ or $01010101010101010101$. So

# NOT P AND NOT Q = $2$.

So # of P or Q = #all - #NEITHER( P nor Q) = #all - #BOTH NOT P AND NOT Q = $2^{20} - 2$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.