One million (1000000) people receive an e-mail with the following message:

- If *exactly* one of you will reply to this e-mail, everyone of you will win 100\$. In any other case, everybody will win nothing.

Suppose that the people receiving this e-mail are all very intelligent, they are willing to win the prize, and they cannot comunicate with each other. The only thing that they can do is just replying, or not. Ah, the e-mail is not SPAM, it is serious :)

What is the best strategy that they can adopt to maximize the probability of succeding? What is (more or less) the probability of success?

Update (20/03/2008): Solution posted! (show solution)

All the receivers of the message cannot communicate with each other, and the only thing that they can do to interact with the problem is replying, or not. So let's say that each of them will reply with probability $p$ (the probability is the same for everyone), and let's calculate how likely it is that exactly one of them will reply. Let $n$ ($=1000000$) be the number of people in the problem, let's chose one of them and let's calculate the probablity the he will be the only one that answers. This probability will be $p(1-p)^{n-1}$, adding this quantity over all the people gives us the probability of success $S(p) = np(1-p)^{n-1}$.

Since we want to maximize it, let's calculate:

$$ \frac{d}{dp}S(p) = n(1-p)^{n-1} + np(n-1)(1-p)^{n-2}(-1) =$$

$$ = n(1-p -(n-1)p )(1-p)^{n-2} =$$

$$ = n(1-np)(1-p)^{n-2} $$

So, $ \frac{d}{dp}S(p) = 0$ is solved by $p=1/n$ or $p=1$, and $p=1$ is surely not a maximum. Thus, the best strategy is replying with probability $1/n$, and the probability of success is:

$$ S(1/n) = n\frac{1}{n}(1-\frac{1}{n})^{n-1} = $$

$$ = n\frac{1}{n}(1-\frac{1}{n})^{n-1} \approx e^{-1} (n\rightarrow\infty).$$
## 2 comments:

a very clever solution

just a joke :)let 's suppose that any mail arrives in the same moment it is sent. if one reply to all recipient he is 'almost-sure' that no other lucky people had replied at the same moment.

:-)

BTW, i'm sure that no solution could ever work in the real world. I mean, some idiots would surely reply in any case, and you could do nothing to prevent it :)

Post a Comment