Problem:
Each of balls is randomly placed into one of bins. Which of the following is closest to the probability that each of the bins will contain an odd number of balls?
Answer Choices:
A.
B.
C.
D.
E.
Solution:
When an odd number of balls are dropped into three bins, the parities of the bins' contents are either odd-odd-odd or even-even-odd (in some order). Consider dropping the balls one at a time. Let be the probability that each of the bins contains an odd number of balls (state odd-odd-odd) after balls have been deposited. Then , and can be computed from by considering what happens with the next 2 balls. With probability the state is currently odd-odd-odd, and there are 9 equally likely ways for 2 more balls to land. With probability they will land in the same bin and the new state will be odd-odd-odd. With probability the state is currently even-even-odd, and 2 of the 9 possibilities for the next 2 balls will change the state to odd-odd-odd. Therefore
which simplifies to
This linear recurrence can be solved by assuming that for some constants , and . Because , it follows that . Because
it follows that . Because
it follows that . Solving this system of equations gives , and . Therefore
The recurrence and initial condition are satisfied by this formula for , so the assumption about the form of was justified. The problem asks for , which nearly equals because the first term is very close to 0 .
Let and represent parities odd and even. Because the number of balls is odd, there are only 4 possible parity states of the three bins: , and . The problem asks for the approximate probability that the state is . If the number of balls is sufficiently large, the probability that the first bin has an even number of balls is very nearly . The same holds for the second bin. Thus , and are all approximately equally likely for the parities of the first two bins. The parity of the third bin is completely determined by the parities of the first two bins because the total number of balls is odd. Thus the probability of each of the 4 parity states is about .
If the balls are placed randomly into the bins one at a time, after balls are placed, either
Note that if all three bins currently contain the same parity of balls, they will surely not contain the same parity once another ball is added to any bin. However, if two bins currently contain the same parity of balls and the third bin contains the other parity, a ball added to the third bin will make all three bins contain the same parity, but one added to either of the first two bins will result in two of the bins having the same parity but not the remaining bin.
Let represent the probability that all three bins contain the same parity of balls. From the reasoning above, Assuming that approaches a limit as , the recurrence implies that , from which it follows that . Therefore should be close to .
The problems on this page are the property of the MAA's American Mathematics Competitions