probability that given n balls and 60 urns no urn has more than 1 ball

Question

A carnival game is set up so that a ball put into play has an equal chance of landing in any of 60 different slots. The operator of the game allows you to choose any number of balls and put them all into play at once. If every ball lands in a separate slot, you receive $1 for each ball played; otherwise, you win nothing. How many balls should you choose to play in order to maximize your expected winnings?

I believe that the equation for the expected winnings = (balls played)*(1-P(2 or more balls in same urn)). Since everything else is relatively straightforward, I want to find this P(2 or more balls in same urn). Is there a certain way of finding this? Or even better, is there a general form to find this probability given n balls and m urns?

Answer 1

The probability that if you use $k$ balls and $60$ urns, the balls will land in different urns is $$\frac{(60)(59)(58)\cdots (60-k+1)}{60^k}.$$

Answer 2

This is equivalent to the birthday problem. Assume you through $n$ balls, with of course $n\le60$. Then

1. Possible outcomes. For every ball there are $60$ possible results (slots that the ball will land), so that there $$60^n$$ possible outcomes.
2. Favourable outcomes. For the first ball you have $60$ possible for the second $59$ and so on, until the n-th ball where you have $60-n$ possible slots, so that there are $$60\cdot59\cdot\ldots\cdot(60-n+1)=\frac{60!}{(60-n)!}$$ favourable results.

In sum, the probability of winning when throwing $n$ balls is equal to $$P(\text{Win})=\frac{60!}{(60-n)!60^n}=\frac{n!\dbinom{60}{n}}{60^n}$$ (see also the respective result in Wikipedia link). Therefore your expected win $E[W]$ is equal to $$E[W]=n\cdot P(\text{Win})+0\cdot[1-P(\text{Win})]=nP(\text{Win})$$ That is you want to solve the maximization problem $$\max_{n} \frac{n\cdot60!}{(60-n)!60^n}$$

---

Worst case: There are 60 possible values of $n$, so start plugging in in an Excel worksheet and you will find the minimum pretty soon.

---

Answer: $n=8$ with expected return $4.91$