Win a copy of Serverless Applications with Node.js this week in the NodeJS forum!
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Liutauras Vilda
  • Bear Bibeault
  • Jeanne Boyarsky
  • paul wheaton
Sheriffs:
  • Junilu Lacar
  • Paul Clapham
  • Knute Snortum
Saloon Keepers:
  • Stephan van Hulst
  • Ron McLeod
  • Tim Moores
  • salvin francis
  • Carey Brown
Bartenders:
  • Tim Holloway
  • Frits Walraven
  • Vijitha Kumara

When bored on a rainy wednesday afternoon  RSS feed

 
Rancher
Posts: 3127
110
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
The other day I found a puzzle on the internet, that loooked simple to solve, at first. Hmm, it was more involved than I expected, and it made me to rehearse some long forgotten maths. I had a lot of fum solving it. But don't worry, this forum is all about programming, so read on. You will not be bored, I guarantee, or else you will be entitled for a refund   ;)

The situation is this: we have six unbiased coins. Now, in round 1 we toss them all, and remove all those that landed heads up. In round 2 we toss all the remaining coins, remove again all those landing head op, et cetera, until there are no more coins left. The question is: what is the average number of rounds?

Question 1
can you write code that simulates this process? Give for N in the range (1, 1000) the average number of rounds. To test your outcomes: the average is (very) roughly equal to 1.5 + base_of_2_log(N), where N is the starting number of coins.

Question 2
But we can derive the discrete density function. To save on typing, let v = 0.5, the chance for a coin to land on heads. If we have one coin, then the chance of needing k tosses is v^k. We get as average the series

E(1) = 1*v + 2*v^2 + 3*v^3 + ... (ad infinitum).

If you are a little handy in manipulating this kind of series, you will have no difficulty to find that E(1) = 2.
If we have N coins, and the random variable X(i) denotes the number of tosses needed for coin i, then we are looking for the density of the random variable Y = max(X(1), X(2), ..., X(n)). We get:

the chance that Y = k, or P[Y = k], = [1 - v^k]^N - [1 - v^(k - 1)]^N.

(Note: in the derivation of this formula, you might get the factor v / (1 - v). But since this is equal to 1, I left it out).

Can you give a good approximation of the average, from the definition of it and the above formula, for number of coins 1 ... 1000, and compare these to the outcomes of challenge 1?

Question 3
For small values of N, a perhaps easier way is as follows. Suppose we have 1 coin. Then for sure we toss 1 time. And with a chance of v the coin is landing tails up, and we have the same situation as before. That leads to the simple formula:

E(1) = 1 + v*E(1), and so we find that E(1) = 2.

When we have two coins, things get slightly more complex. We get the following formula:

E(2) = 1 + (2 * v^2 * E(1)) + (v^2 * E(2)). Solving this, we get that E(2) = 8 / 3.

And proceeding this way, we arrive at the lovely recursion relation:

           (N)                (N)                      (N)
E(N) = 1 + (1) * v^N * E(1) + (2) * v^N * E(2) + ... + (N) * v^N * E(N)

      (N)
where (K) is the well known N over K, equalling N! / (K! * (N - K)!), these are also the numbers in Pascals Triangle.

How would you code this? And what is the answer when we have six coins?

Happy coding!
 
What does a metric clock look like? I bet it is nothing like this tiny ad:
global solutions you can do in your home or backyard
https://coderanch.com/t/708587/global-solutions-home-backyard
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!