Problem:
A box contains twelve balls, each of a different color. Every minute, Randall randomly draws a ball from the box, notes its color, and then returns it to the box. Consider the following two conditions:
(1) Some ball has been drawn at least twelve times (not necessarily consecutively).
(2) Every ball has been drawn at least once.
What is the probability that condition (1) is met before condition (2)? If the correct answer is and your answer is , you get points.
Solution
Solution:
Below is a python implementation to compute the probability, using the same method as the solution to the easier version (with three balls).
```
from fractions import Fraction
N = 12
probs = [{} for i in range((N-1)*(N-1)+2)]
prob1 = Fraction()
prob2 = Fraction()
init = tuple(0 for i in range(N))
probs[0][init] = Fraction(1,1)
for i in range((N-1)*(N-1)+1):
for t in probs*:
for j in range(N):
val = probs*[t] * Fraction(1,N)
l = list(t)
l[j] += 1
l.sort()
l = tuple(l)
if (l[-1] == N):
prob1 = prob1 + val
elif (l[0] == 1):
prob2 = prob2 + val
else:
probs[i+1][l] = probs[i+1].setdefault(l, Fraction()) + val
print(prob1)
```
Intuitively the probability should be quite small, since the distribution tends towards the second condition instead of the first. Indeed, the exact fraction is , where
Want a route through all this instead of an archive? The track
puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.