Author |
Topic: Randomly Orring (Read 445 times) |
|
k2xl
Newbie
  
Posts: 17
|
 |
Randomly Orring
« on: Feb 18th, 2008, 10:33am » |
 Quote  Modify
|
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
|
| « Last Edit: Feb 18th, 2008, 11:13am by k2xl » |
 IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender: 
Posts: 13730
|
|
Re: Randomly Orring
« Reply #1 on: Feb 18th, 2008, 11:10am » |
Quote Modify
|
I'd guess N/N + N/(N-1) + N/(N-2) + ... + N/1
Not quite sure, though..
|
| « Last Edit: Feb 18th, 2008, 11:10am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
rmsgrey
Uberpuzzler
  
Gender:
Posts: 2873
|
|
Re: Randomly Orring
« Reply #2 on: Feb 18th, 2008, 1:10pm » |
Quote Modify
|
on Feb 18th, 2008, 11:10am, towr wrote:I'd guess N/N + N/(N-1) + N/(N-2) + ... + N/1
Not quite sure, though.. |
|
That's what I get too, using the fact that each transition time is independent of the previous transition times.
|
|
IP Logged |
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: Randomly Orring
« Reply #3 on: Feb 18th, 2008, 6:48pm » |
Quote Modify
|
This is a classic problem.
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print