Author |
Topic: A counting problem (Read 1627 times) |
|
nirmal.mehta
Newbie
Posts: 1
|
 |
A counting problem
« on: Aug 23rd, 2007, 12:47pm » |
 Quote  Modify
|
How many bit strings of length 8 have either three consecutive 0s or four consecutive 1s?
rather than knowing the answer i am more interested to find out how these kind of counting problems be attacked?
Thanks
|
|
 IP Logged |
|
|
|
ThudnBlunder
Uberpuzzler
The dewdrop slides into the shining Sea
Gender: 
Posts: 4489
|
|
Re: A counting problem
« Reply #1 on: Aug 23rd, 2007, 1:16pm » |
Quote Modify
|
Scratching the rust from my brain, I think
there are (8 - 3 + 1)*28-3 = 196 ways of having 3 or more consecutive 0's
and
there are (8 - 4 + 1)*28-4 = 80 ways of having 4 or more consecutive 1's
and
there are 2*28-3-1 + (8 - 3 + 1 - 2)*28-3-2 = 64 ways of having exactly 3 consecutive 0's
and
there are 2*28-4-1 + (8 - 4 + 1 - 2)*28-4-2 = 28 ways of having exactly 4 consecutive 1's.
|
| « Last Edit: Aug 23rd, 2007, 6:02pm by ThudnBlunder » |
IP Logged |
THE MEEK SHALL INHERIT THE EARTH.....................................................................er, if that's all right with the rest of you.
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: A counting problem
« Reply #2 on: Aug 24th, 2007, 2:03am » |
Quote Modify
|
I get different figures than T&B. Here’s my line of reasoning.
Let Z3(n) be the number of n-bit strings with the property that no 3 consecutive bits are zeros. Then, we want to find 28 – Z3(8).
If X is such a string, than it has one of the forms 1Y, 01Z, 001W, where Y, Z, W are strings satisfying the above condition with lengths n-1, n-2, n-3 respectively. It then becomes clear than Z3(n) satisfies the following recursive equation:
Z3(n) = Z3(n-1) + Z3(n-2) + Z3(n-3)
with Z3(0) = 1, Z3(1) = 2, Z3(2) = 4 (why?). But then, Z3(n) equals (n+2)-th Tribonacci Number. Therefore, Z3(8) = 149, and the number of required strings (with at least 3 consecutive zeros) is 107.
Similarly, the number of 8-bit strings with at least 4 consecutive ones may be computed using Tetranacci Numbers, and turns out to be 48.
In order to answer the original question, we need to compute also the number of strings having both sequences as substrings. I counted 8.
So, finally, the answer is 107+48-8 = 147.
|
|
IP Logged |
|
|
|
ThudnBlunder
Uberpuzzler
The dewdrop slides into the shining Sea
Gender:
Posts: 4489
|
|
Re: A counting problem
« Reply #3 on: Aug 25th, 2007, 12:03pm » |
Quote Modify
|
Obviously I didn't scratch hard enough.
Now that you mention it, I remember the Fibonacci solution.
I must say, Barukh, for a non-mathematician you are extremely erudite. 
|
| « Last Edit: Aug 25th, 2007, 1:34pm by ThudnBlunder » |
IP Logged |
THE MEEK SHALL INHERIT THE EARTH.....................................................................er, if that's all right with the rest of you.
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: A counting problem
« Reply #4 on: Aug 25th, 2007, 11:35pm » |
Quote Modify
|
on Aug 25th, 2007, 12:03pm, ThudanBlunder wrote:| I must say, Barukh, for a non-mathematician you are extremely erudite. |
|
Thanks, T&B! It's a real pleasure to hear this from you. 
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print