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!