Win a copy of 97 Things Every Java Programmer Should Know this week in the Java in General 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 ...
  • Campbell Ritchie
  • Paul Clapham
  • Jeanne Boyarsky
  • Junilu Lacar
  • Henry Wong
  • Ron McLeod
  • Devaka Cooray
  • Tim Cooke
Saloon Keepers:
  • Tim Moores
  • Stephan van Hulst
  • Frits Walraven
  • Tim Holloway
  • Carey Brown
  • Piet Souris
  • salvin francis
  • fred rosenberger

When bored on a rainy wednesday afternoon

Posts: 3959
  • 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)

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!
If you settle for what they are giving you, you deserve what you get. Fight for this tiny ad!
Devious Experiments for a Truly Passive Greenhouse!
    Bookmark Topic Watch Topic
  • New Topic