3
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

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}.$$

$\endgroup$
  • $\begingroup$ So the general form is $\frac{(m)(m-1)(m-2)...(m-k+1)}{m^k}$? Ok, I have a feeling I've seen this somewhere before, but I probably forgot... And anyways, using this formula the answer is 8 which is correct. $\endgroup$ – Kevin Mar 29 '14 at 20:23
  • $\begingroup$ Yes, that is correct. It is not difficult. There are $m^k$ equally likely ways the balls can land. (Think of the balls as thrown one at a time.) Now count the favourables, where no two land in the same place. The first ball can go into any of the $m$ slots. For every choice of where the first ball goes, there are $m-1$ "legal" places for the second ball to go. And for every legal choice for the first two balls, there are $m-2$ legal places for the third ball, and so on. The Birthday Problem uses the same counting technique. $\endgroup$ – André Nicolas Mar 29 '14 at 20:28
2
$\begingroup$

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$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.