Minimario's strings of length 10

Find the number of binary strings of length 10 with no two consecutive 1s.

This problem is shared by Minimario M.

Details and assumptions

A binary string is a sequence of integers that are 1 1 or 0 0 . The length of a string refers to the number of integers in it.

As an explicit example, the binary string of length 3 3 are 000 , 001 , 010 , 011 000, 001, 010, 011 , 100 , 101 , 110 , 111 100, 101, 110, 111 .


The answer is 144.

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

19 solutions

Sayantan Guha
Nov 25, 2013

Let the starting digit (1st digit) be 1. (1 possibility for 1st place) In that case the second digit has to be 0. (1 possibility for 2nd place ) So the third digit can be either 0 or 1 (2 possibilities for 3rd place). If the third digit is 1 then the 4th digit has to be 0 & if the third digit is 0 then the 4th digit can be 0 or 1. (3 possibilities for 4th place). Similarly checking corresponding digits for 0 & 1 we get the following: (5 possibilities for 5th place), (8 possibilities for 6th place), (13 possibilities for 7th place), (21 possibilities for 8th place), (34 possibilities for 9th place) & (55 possibilities for 10th place). The possibilities go as in a Fibonacci sequence. So when the starting digit is 1 the number of possibilities is 55. When the starting digit is 0 and the 2nd digit is 1, the last possibility is eliminated & we get 34 choices. When the 1st two starting digits are 0 and the 3rd digit is 1, then the last two possibilities get eliminated & we get 21 choices. Proceeding in this way when the 1st seven digits are zero and the 8th digit is 1, the last seven possibilities get eliminated & we get 2 choices viz 0000000,100; 0000000,101. When the 1st eight digits are zero and the 9th digit is 1, the last eight possibilities get eliminated & we get 1 choice viz 00000000,10. When the 1st nine digits are zero the last nine possibilities get eliminated & we get 1 choice viz 000000000,1. Then there is the last case where all digits are 0's. So ultimately we get 1+1+1+2+3+5+8+13+21+34+55=144 This most probably would seem like an overly complex process but its how I did the sum...

Just an observation: When we count for small cases, starting from binary strings of length 1, we find that the number of strings with no two consecutive 1's is 2. For length = 2, the number of strings with no two consecutive 1's is 3. Similarly, for length = 3, we get 5. Proceeding up to length = 10, the number of strings with no two consecutive 1's for each case are: 2, 3, 5, 8, 13, 21, 34, 55, 89, 144. The Fibonacci pattern.

Sean Gee - 7 years, 6 months ago

Log in to reply

Yup.

William Cui - 7 years, 6 months ago

great! Thx for sharing!!!

Rutvik Paikine - 7 years, 6 months ago

What I did was listed it out. I feel stupid.

Gabriel Seng - 7 years, 6 months ago

Log in to reply

Yeah, same, except a program listed them out for me.

William Cui - 7 years, 6 months ago

Maybe next time, I should change the 10 into a larger number ._.

@below, note that mathematics \ne data structures and algorithms

minimario minimario - 7 years, 6 months ago

Amazing

Henrique Checcucci - 7 years, 6 months ago

Consider the last digit of a n n -digit bit string.

If it is a 1, then the 2nd to last digit must be a 0, and the string is just a ( n 2 ) (n-2) digit bit string with 01 01 attached at the end of it.

If it is a 0, then the string is a ( n 1 ) (n-1) digit bit string with 0 0 attached to the end of it.

Note that these 2 cases will not overlap and will count everything.

Therefore, we obtain a recursion.

Let S n S_n be the number of strings of length n n .

Creary, S 1 = 2 S_1=2 and S 2 = 3 S_2=3 .

Therefore, S 3 = 5 , S 4 = 8 , S 5 = 13 , S 6 = 21 , S 7 = 34 , S 8 = 55 , S 9 = 89 S_3=5, S_4=8, S_5=13, S_6=21, S_7=34, S_8=55, S_9=89 , and S 10 = 144 S_{10}=\boxed{144} . Notice that these are the fibonacci numbers.

same approach!

Cody Martin - 7 years, 6 months ago

Wow!!!!!!!

Krystal D'Souza - 7 years, 6 months ago
Freddy Román
Jul 22, 2013

Let f ( n ) f(n) be the number of binary strings of length n n with no two consecutive 1 1 s. f ( 0 ) = 1 f(0) = 1 , and f ( 1 ) = 2 f(1) = 2 .

Consider n > 1 n > 1 . If a 1 1 is added at the beginning of the string, then the next digit must be 0 0 . That means that the number of strings with length n n which start with a 1 1 is f ( n 2 ) f(n-2) . If a 0 0 is added instead, there is no restriction on the next digit; the number of strings with length n n which start with a 0 0 is f ( n 1 ) f(n-1) .

Putting this together leaves us with the recursive formula: f ( n ) = f ( n 2 ) + f ( n 1 ) f(n) = f(n-2) + f(n-1) Which is the same recurrence as the Fibonacci sequence, shifted by two.

Therefore, the answer we want is the 12 12 th Fibonacci number: 144 144 .

Malavika Dinaker
Feb 17, 2014

For the 1s not to be together, you have to have a minimum of 5 0s.

For 5 0s: -0-0-0-0-0- So you can put the 5 1s in the remaining places (represented by hyphens) in 6C5 ways.

For 6 0s: -0-0-0-0-0-0-0- So you can put the 4 1s in the remaining places in 7C4 ways.

Similary for 7, 8, 9 and 10 0s.

Therefore the total is: 6C5 + 7C4 + 8C3 + 9C2 + 10C1 + 11C0 = 144

I forgot 11C0

Vighnesh Raut - 6 years, 2 months ago
Kelly Milla
Nov 27, 2013

by listing at least 5 binary numbers without two consecutive 1's we can get the ff:

0001 - 1st binary number without two consecutive 1's

0010 - 2nd

0100 - 3rd

0101 - 4th

1000 - 5th

by noticing the pattern we can get that:

           pattern                  |        Original Binary Number

   13  8   5   3   2    1           |       32 16   8   4   2   1

   0   0   0    0   0   0           |       0   0   0   0   0   0

the sequence is known as the Fibonacci Sequence

in this case:

fib(1) = 1

fib(2) = 2

fib(n) = fib(n-1)+fib(n-2)

Example:

 Find the number of binary strings of length 5 with no two consecutive 1's.

 the answer would be fib(5+1) which is fib(6) = 13.

 since the maximum value of binary number with no 2 consecutive 1's is 

"10101" - which has the value  (1*8) + (0*5) + (1*3) + (0*2) + (1*1) = 12

 and since we have to include "00000" - 12 + 1 = 13

in the given problem to find the number of binary strings of length 10 with no two consecutive 1's.

the answer would be f(10+1) = f(11) = 144.

Nico Stirling
Nov 27, 2013

We can make a table with length of the string compared to the number of them that fit the condition, for the first few lengths (because it is quite easy to count these) to find the pattern of the number of them. Then we just continue this pattern until we reach the length 10.

(Length, Number): (1,2), (2,3), (3,5), (4,8), (5,13)

After these first few terms we see that Number follows the Fibonacci sequence, so we can just continue the Fibonacci until the term that corresponds to length 10.

(Length, Number): (6,21), (7,34), (8,55), (9,89), (10,144)

So the answer is 144 \boxed{144}

Bob Bobson
Jul 27, 2013

Let f ( n ) f(n) be the number of such binary sequences of length n n . Suppose we know the values f ( k ) f(k) and f ( k + 1 ) f(k+1) then sequences of length k + 2 k+2 either end in a 0 0 and then have any valid sequence of length k + 1 k+1 preceding it, or end 01 01 with any sequence of length k k preceding it. These are the only possibilities so f f satisfies the recursion relation

f ( n + 2 ) = f ( n ) + f ( n + 1 ) . f(n+2) = f(n) + f(n+1).

We clearly have the initial cases f ( 0 ) = 1 f(0) = 1 and f ( 1 ) = 2 f(1) = 2 and from this we can compute f ( 10 ) = 144 \boxed{f(10) = 144} .

Hieu Pham
Jul 23, 2013

We consider the sequence to have 10,9,8...5 0s respectively, the sequence can't have less than 5 0s cuz in that case there would be at least 2 1s are next to each other. Now we put the remaining 1s into the 'spaces' between the 0s including the 2 ends, and the number of 'spaces' equal the number of 0s + 1, so we have 10C0 + 10C1 + 9C2 + 8C3 + 7C4 + 6C5 = 144

Gardar Sigurdsson
Jul 25, 2013

There can only be at most five ones in the binary string so we have six cases. We imagine the crosses as zeros and the lines between them as ones. For example |xx|xxx|x| translates to 1001000101. If there are five crosses we can choose between six spots to place 10 5 = 5 10 - 5 = 5 lines. We can do that in 6 ! ( 6 5 ) ! × 5 ! = 6 \frac{6!}{ ( 6 - 5 )! \times 5!} = 6 ways. Generally, if there are n n crosses we can choose between n + 1 n + 1 spots to place 10 n = 5 10 - n = 5 lines. We can do that in ( n + 1 ) ! ( ( n + 1 ) ( 10 n ) ) ! × ( 10 n ) ! \frac{ (n+1)! }{ ( ( n + 1 ) - ( 10 - n ) )! \times ( 10 - n )!} ways. We add together the ways to arrange the crosses and lines for 0,1,2,3,4 and 5 crosses (Note 0 ! = 1 0! = 1 ):

6 ! ( 6 5 ) ! × 5 ! + 7 ! ( 7 4 ) ! × 4 ! + 8 ! ( 8 3 ) ! × 3 ! + 9 ! ( 9 2 ) ! × 2 ! + 10 ! ( 10 1 ) ! × 1 ! + 11 ! ( 11 0 ) ! × 0 ! = 6 + 35 + 56 + 36 + 10 + 1 = 144 \frac{6!}{ ( 6 - 5 )! \times 5!} + \frac{7!}{ ( 7 - 4 )! \times 4!} + \frac{8!}{ ( 8 - 3 )! \times 3!} + \frac{9!}{ ( 9 - 2 )! \times 2!} + \frac{10!}{ ( 10 - 1 )! \times 1!} + \frac{11!}{ ( 11 - 0 )! \times 0!} = 6 + 35 + 56 + 36 + 10 + 1 = 144

why we have maximum five ones?

Lvly Tapan - 7 years, 10 months ago
Daniel Leong
Jul 25, 2013

I COUNTED THEM

Let's say we know the sequences that satisfy the problem for length n - 1 (in this case 9 bits). So the number of strings that satisfy the problem of length n is the sum of:

  • the number of strings that satisfy the problem of length n - 1(just put 0 at the end)

  • the number of strings that satisfy the problem of length n - 1 that end with 0 (put 1 at the end)

Since for n = 1 there are 2 possibilities (one ending with 0 and the other with 1) and (letting f(n) denote the number we seek)

f(n) = f(n - 1) + f(n - 2) (if we define f(0) = 1).

So the number of strings is the (n + 1)th fibonacci number given f(0) = 1 and f(1) = 2 f(10 + 1) = f(11) = 144

I found the solution folowing a thinking similar to Ivan Henrique, I think his explanation is the easiest I found. Anyway, the solution is based on Fibonacci numbers

Vali Dobre - 7 years, 10 months ago

Let B ( n ) B(n) be the number of binary strings of length n n with no two consecutive 1's.

When n = 1 n=1 , there are 2 2 strings: 0 0 and 1 1 , When n = 2 n=2 , there are 3 3 strings: 00 00 , 01 01 , and 10 10 When n = 3 n=3 , there are 5 5 strings: 000 , 001 , 010 , 101 , 000, 001, 010, 101, and 100 100 . When n = 4 n=4 , there are 8 8 strings: 0000 , 0001 , 0010 , 0101 , 0100 , 1000 , 1001 , 1010 0000, 0001, 0010, 0101, 0100, 1000, 1001, 1010 . We notice that B ( 3 ) = B ( 2 ) + B ( 1 ) B(3)=B(2)+B(1) , and B ( 4 ) = B ( 3 ) + B ( 2 ) B(4)=B(3)+B(2) For all the binary strings of length j j , there exists a binary string of length j + 1 j+1 : this is because we can put a 0 0 before the binary string and ensure that no consecutive 1's are present. This takes care of all binary strings that start with a 0 0 . For the binary strings that start with 1 1 , the next digit must be 0 0 , and we must have a binary string of length j 2 j-2 . This is just B ( j 2 ) B(j-2) Therefore, B ( j ) B(j) is simply equal to B ( j 1 ) + B ( j 2 ) B(j-1)+B(j-2) . Therefore, B ( 5 ) = B ( 4 ) + B ( 3 ) = 8 + 5 = 13 B(5)=B(4)+B(3)=8+5=13 B ( 6 ) = B ( 5 ) + B ( 4 ) = 13 + 8 = 21 B(6)=B(5)+B(4)=13+8=21 B ( 7 ) = B ( 6 ) + B ( 5 ) = 21 + 13 = 34 B(7)=B(6)+B(5)=21+13=34 B ( 8 ) = B ( 7 ) + B ( 6 ) = 34 + 21 = 55 B(8)=B(7)+B(6)=34+21=55 B ( 9 ) = B ( 8 ) + B ( 7 ) = 55 + 34 = 89 B(9)=B(8)+B(7)=55+34=89 B ( 10 ) = B ( 9 ) + B ( 8 ) = 89 + 55 = 144 B(10)=B(9)+B(8)=89+55=\boxed{144}

The maximum amount of ones is five, the minimum amount is zero. When there are five ones, we can choose a set of five of six possible spaces. Doing the same analysis the equation is: ( 6 5 ) + ( 7 4 ) + ( 8 3 ) + ( 9 2 ) + ( 10 1 ) + 1 = 144. {6 \choose 5} + {7 \choose 4} + {8 \choose 3} + {9 \choose 2} + {10 \choose 1} + 1 = 144.

why we have maximum five ones?

Lvly Tapan - 7 years, 10 months ago

Log in to reply

If have more of five ones, will always two consecutive 1s. Sorry for bad english.

Víctor Mandujano Gutierrez - 7 years, 10 months ago
Hemang Sarkar
Jul 22, 2013

it is easy to see that the number of zeroes we can use ranges from 10 10 to 5 5 .

because we must have at least one zero in between any two consecutive ones. and for the rest of the cases where we have less than 5 5 zeroes, the number of spaces between the ones is more than the number of zeroes.

case 1 1 : we have 10 10 zeroes. so 1 1 for this case.

case 2 2 : we have 9 9 zeroes and 1 1 one.

0 0 0 0 0 0 0 0 0

we have 10 10 places to place that one.

so this case counts for C ( 10 , 1 ) = 10 C(10,1) = 10 .

so we got the trick. we first place the zeroes and then we put the ones.

and when we are using x x zeroes, the number of available spaces is x + 1 x+1 .

the answer is thus 1 + C ( 10 , 1 ) + C ( 9 , 2 ) + C ( 8 , 3 ) + C ( 7 , 4 ) + C ( 6 , 5 ) = 144 1 + C(10,1) + C(9,2) + C(8,3) + C(7,4) + C(6,5) = 144

Vinay Chindu
Jul 22, 2013

Let Sk be the set of all binary strings of length k with no two consecutive 1s . To obtain binary strings of length k+1 , either append 0 to every string of set Sk or append 0 and then append 1 to every string of set Sk-1 . Hence, n(Sk+1) = n(Sk) + n(Sk-1) . It is a Fibonacci sequence. n(S10) = F(10) with F(1) = 2, F(2) = 3

Ankur Verma
Jul 22, 2013

Basically it is fibonacci series where we can analyze the given question by factoring in the following aspects: Let Sn be the set of binary sequences of length n. Note that |Sn| = 2n.

Let Fn be the set of sequences of binary sequences of length n that do not contain two consecutive 1 bits. The Kata asks us to determine |Fn|. I'll call that f(n).

By inspection, it's easy to work out the first few values of f(n). Note that when n=0, we can count the empty sequence. so here we have a fibonacci series having terms as 1 as f(0),2 as f(1),3 as f(2),5 as f(3),8 as f(4),13 as f(5),21 as f(6),34 as f(7),55 as f(8),89 as f(9),144 as f(10) and hence when n= 10 we can find the value of f(10) through this series which comes out to be 144

Quang Minh Bùi
Jul 22, 2013

At the n t h n^{th} number of the string, let a n a_n and b n b_n is the number of cases that n t h n^{th} number is 0 and 1 respectively. If the previous number ( ( n 1 ) t h (n-1)^{th} number) is 0, so n t h n^{th} number can be 0 or 1, otherwise, it can be only 0. Therefore:

a n = a n 1 + b n 1 a_n = a_{n-1} + b_{n-1}

b n = a n 1 b_n = a_{n-1}

And the total number of cases which is also the number of string of length n, is the sum of these two variables:

S n = a n + b n = a n + 1 S_n = a_n + b_n = a_{n+1}

Apply the above equation, we have:

S n = a n + b n = a n + a n 1 = S n 1 + S n 2 S_n = a_n + b_n = a_n + a_{n-1} = S_{n-1} + S_{n-2}

At the first number, there is two cases: 1 and 0, thus S 1 = 2 S_1 = 2 , a 1 = 1 a_1 = 1 , b 1 = 1 b_1 = 1 .

At the 2nd number, S 2 = a 2 + b 2 = S 1 + a 1 = 2 + 1 = 3 S_2 = a_2 + b_2 = S_1 + a_1 = 2 + 1 = 3

At the 3rd number, S 3 = S 2 + S 1 = 2 + 3 = 5 S_3 = S_2 + S_1 = 2 + 3 = 5

Therefore, at the 10th number, S 10 = 144 S_{10} = 144 and it is also the solution of this problem.

Jerry Yu
Jul 21, 2013

One can see the Fibonacci pattern by writing out the number of possibilities for lengths 1, 2, 3, 4...

length 1 : 0,1

length 2 : 00,01,10

length 3 : 000,001,010,100,101

...

Thus one can see the Fibonacci pattern: 2,3,5,8,13,21,34,55,89, 144 . The answer for a binary string with length 10 is 144

Rizky Dermawan
Jul 21, 2013

Let start from binary string with length 1, you will get 2 strings. With length 2, you will get 3 strings. With length 3, you will get 5 strings. With length 4, you will get 8 strings. With length 5, you will get 13 strings. With this, we deduce that the number of strings is like fibonacci sequence, where binary string with length n, you will get F n + 2 F_{n+2} . Now, we can find how many of binary strings with length 10 = F 12 = 144 F_{12}=144

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...