So You Think You Can Count? (Math Challenge)

[JefPlays]

Then give me an answer to this:

 

How many binary strings are there with n digits that do not have 11000 as a substring?

 

(To clarify, a binary string is any sequence of 1's and 0's, I'm asking how many there are that do not contain the sequence 11000 in that order.)

 

Note: This is not something I need for an assignment. I know how to solve this. I just want to give you something to think about on your lunch break :)

 

No rewards for this, just for kicks and bragging rights. Have fun!

 

EDIT: Spotted an error in my question. Revised to give a finite answer.

Edited July 3, 2015 by Jeffrey94

[DeMonkey]

Lots.

[Diun]

It seems to me that there are too many unique strings to count, unless I read this wrong. 1. 11. 111. 1111. Etc.

[Autongnosis]

Technically speaking shouldn't it be an absurd number? Something like infinite minus one? Considering the fact that unless you put on limitation you can create endless sequences of simply 0101 and so on, none of which contain that string, by adding another 0 (if last was 1) or 1 (if last was 0) at the end of the string

[AlphaSierraMike]

Let's assume that it's a 32-bit string, since that's the most common.

 

So let's start with 2^32 as the max amount of combination.

 

 

1. Now the first combination that has 11000 is... 11000. So that's one.

 

2. Moving on to the next digit, 110000 and 110001, that's two....

 

3. Moving on, 1100000, 1100001, 1100010, 1100011, that's four....

 

the trend is the power of two and by the power of n-1, 2^(n-1)

 

if the trend keeps going, it should reach 28 numbers, so using geometric progression to tally up the amount of numbers containing 11000.... 1 + 2 + 4 + 8..... 2^27 = (2^28-1)/(2-1)

 

So the answer is....2^32 - 2^28 + 1, whatever that ends up being.

 

Edit - The number should be off, since the way I'm calculating assumes the digit leads with 11000, but it could be 111000 and it would still be true.

 

but that's all I've got at the moment. I've got other ideas, but they all have the same problem of overlapping, when the number 11000 doesn't strictly appear only when it's specified, it can be arranged randomly from 1s and 0s.

Edited July 3, 2015 by AlphaSierraMike

[Dawn11715]

wait, so are we talking about bit codes with  the length of 8 characters?

In that case 

 it would be 2^8 - NUMBER_OF_STRINGS_THAT_CONTAINS_THE_SEQUENCE

with NUMBER_OF_STRINGS_THAT_CONTAINS_THE_SEQUENCE= 2^3=8

so its 248 in the end 

 

EDIT:

 

Let's assume that it's a 32-bit string, since that's the most common.

 

Ok, I was thinking of Bytes (which are 8 Bits) but in that case:

 it would be 2^32 - NUMBER_OF_STRINGS_THAT_CONTAINS_THE_SEQUENCE

with NUMBER_OF_STRINGS_THAT_CONTAINS_THE_SEQUENCE= 2^(32-5)

so its something I cant figure out without using a program

Edited July 3, 2015 by Dawn11715

[BluelitHalo]

Let's simplify this and say we're talking about an n-bit binary string with n >= 5.  There are (2^n) possible strings, (n-4) possible placements for the "11000" substring, and (n-5) leftover bits that exclude the potential substring.  The count of how many strings there are that contain the given substring is (2^(n-5))*(n-4), so the count of how many strings EXCLUDE those is (2^n) - ((2^(n-5))*(n-4)).

 

FOR THE ORIGINAL QUESTION:

 

Now let's expand our view to the set of all binary strings with a length of 1 to N bits.  The total count of how many strings in that set excluding "11000" can be written in series form.  So, including the (16 + 8 + 4 + 2 = ) 30 strings in the set of binary strings with a length of 1 to 4 bits...

 

 

... or more simply (intermediate work here http://i.imgur.com/AtciB7d.jpg) ...

 

 

... is the total count.  If you set N to infinity, since your question doesn't state any sort of limit on the length of the binary string, then there will be an infinite count as the answer.

 

EDIT: With the revised question and with further checks, the answer is (2^n) - ((2^(n-5))*(n-4)) for 5 <= n < 10, (2^n) for n < 5.   This isn't considering the strings that have "11000" in multiple places, so I'm excluding more strings than neccesary in my work.

 

Edited July 3, 2015 by Sonitorum

[JefPlays]

So I forgot to specify a size. The answer would have actually been infinitely many!

 

Revised the question. Now you're counting strings with n digits for some positive integer n.