wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> putnam exam (pure math) >> A counting problem
        
(Message started by: nirmal.mehta on Aug 23^rd, 2007, 12:47pm)

Title: A counting problem
Post by nirmal.mehta on Aug 23^rd, 2007, 12:47pm

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

Title: Re: A counting problem
Post by ThudanBlunder on Aug 23^rd, 2007, 1:16pm

Scratching the rust from my brain, I think
there are (8 - 3 + 1)*2^8-3 = 196 ways of having 3 or more consecutive 0's
and
there are (8 - 4 + 1)*2^8-4 = 80 ways of having 4 or more consecutive 1's
and
there are 2*2^8-3-1 + (8 - 3 + 1 - 2)*2^8-3-2 = 64 ways of having exactly 3 consecutive 0's
and
there are 2*2^8-4-1 + (8 - 4 + 1 - 2)*2^8-4-2 = 28 ways of having exactly 4 consecutive 1's.

Title: Re: A counting problem
Post by Barukh on Aug 24^th, 2007, 2:03am

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 2⁸ – 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 (http://mathworld.wolfram.com/TribonacciNumber.html). 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 (http://mathworld.wolfram.com/TetranacciNumber.html), 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.

Title: Re: A counting problem
Post by ThudanBlunder on Aug 25^th, 2007, 12:03pm

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. 8)

Title: Re: A counting problem
Post by Barukh on Aug 25^th, 2007, 11:35pm

on 08/25/07 at 12:03:22, ThudanBlunder wrote:

I must say, Barukh, for a non-mathematician you are extremely erudite. 8)

Thanks, T&B! It's a real pleasure to hear this from you. :D