Binary Strings

Computer Science Level 4

Find the number of binary strings of length 100 which do not contain any two consecutive 1's.

Example

There are $3$ binary strings of length $2$ which do not contain any two consecutive $1$ 's( $00,01,10$ ).

The answer is 927372692193078999176.

3 solutions

Abhishek Sinha
Aug 30, 2015

Let $N^1(n)$ and $N^0(n)$ denote the number of binary strings of length $n$ ending with $1$ and $0$ respectively, such that no consecutive $1$ 's occur. Then it is clear that the following recursion holds $N^1(n+1)=N^0(n)$ $N^0(n+1)=N^1(n)+N^0(n)$ We also have the initial condition that $N^1(2)=1, N^0(2)=2$ The recursions are now fully specified and we require $N^0(100)+N^1(100)=927372692193078999176$

I think you might need to expand a bit - especially when you say "it is clear" and you leap from your values for N1(2) and N0(2) to your final result. As my maths teacher used to say : show your working :-)

Tony Flury - 5 years, 8 months ago

Tony, if you have the means to run Python then run my script, with N=1, N=2, N=3, N=4 and so on. I suspect you'll see the pattern if you do.

Bill Bell - 5 years, 8 months ago

Bill - I can run python (in fact I do development in my spare time). I did look at your code but the python attempt I wrote was cleaner (shorter - although I never got an answer - run time was hours I would imagine) - and I haven;t found the bitarray module

Tony Flury - 5 years, 8 months ago

@Tony Flury – More like a thousand years for mine. And not what I was getting at. What I wrote wasn't meant to be 'clean', it was meant to call in some fast C code. Until I realised what was going on by putting some sample numbers in.

Bill Bell - 5 years, 8 months ago

@Bill Bell – I got my code to work - and generated the result using the iterative Idea above - but I would have never thought to look at the relation between Numbers endiing in 0 and ending in 1

Tony Flury - 5 years, 8 months ago

@Tony Flury – The above solution may be thought of as a very simple instance of Dynamic Programming . The variables $(N^1(n),N^0(n))$ are the ``states" of the program. Picking up the right states is an art and there is no universal method available. Of course, the brute-force approach of just generating the valid sequences won't work even for moderate value of $n$ , say $10000$ , even with the fastest super-computer available, whereas the above method solves the problem in a flash. The beauty of the above recursive solution is that we can actually derive a "closed form" expression for any $n$ using matrix exponentials.

Abhishek Sinha - 5 years, 8 months ago

@Abhishek Sinha – @Abhishek Sinha - how did you identify the correct states in the first place - they would never have occurred to me.

Tony Flury - 5 years, 8 months ago

If $a_{n}$ represents the number of sequence that does have consecutive 11's then we have a closed form as:

$a_{n}=(a_{n-1}+a_{n-2}+2^{n-2})$

$a_{0}=0, a_{1}=1$

So for the question we compute $2^{n}-a_{n}$ for $n\geq2$ . Which is quick to compute.

Beakal Tiliksew - 5 years, 8 months ago

Sayantan Ray
Apr 28, 2018

Let T(n) denotes the solution for binary string of length n. then T(1)=2 T(2)=3 T(3)=5 So on. We can see that it follows the recurrence relation

T(n)=T(n-1)+T(n-2) ,n>2

with base case T(1)=2,T(2)=3

Python Code

a=2

b=3

c=0

for i in range(0,98):

    c=a+b

    a=b

    b=c

print (c)

Output:

927372692193078999176

Bill Bell
Sep 12, 2015

Python 2.7, run on a crude, homemade quantum computer.

How long did this take to run ?

Tony Flury - 5 years, 8 months ago

Please read the note above the code again (and contemplate carefully). ;)

Bill Bell - 5 years, 8 months ago

Binary Strings

The answer is 927372692193078999176.

3 solutions

0 pending reports