wu :: forums - Print Page


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

        riddles >> medium >> Randomly Orring
        
(Message started by: k2xl on Feb 18^th, 2008, 10:33am)

Title: Randomly Orring
Post by k2xl on Feb 18^th, 2008, 10:33am

This is a simple riddle (in terms of a question).

You have N bits (or an array of size N) Assume all the bits (or elements in the array) are set to 0.

You have created a function called Step that will OR a random bit (or element) with 1. This means that if the element or bit is 1 it will stay 1, and if it is 0 it will turn into 1.

How many calls to Step will it take to fill up all the bits with 1's (or how many steps will it take to fill up the array with 1's)?

*Note: Prove your answer by showing values for the first few N values

Title: Re: Randomly Orring
Post by towr on Feb 18^th, 2008, 11:10am

I'd guess [hide]N/N + N/(N-1) + N/(N-2) + ... + N/1[/hide]
Not quite sure, though..

Title: Re: Randomly Orring
Post by rmsgrey on Feb 18^th, 2008, 1:10pm

on 02/18/08 at 11:10:13, towr wrote:

I'd guess [hide]N/N + N/(N-1) + N/(N-2) + ... + N/1[/hide]
Not quite sure, though..

That's what I get too, using the fact that each transition time is independent of the previous transition times.

Title: Re: Randomly Orring
Post by Eigenray on Feb 18^th, 2008, 6:48pm

This is a [link=http://en.wikipedia.org/wiki/Coupon_collector's_problem]classic problem[/link].

Title: Re: Randomly Orring
Post by ThudanBlunder on Feb 18^th, 2008, 7:40pm

http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_easy;action=display;num=1074795531;