You have coins C1, C2, · · · , Cn. For each k, coin Ck is biased so that, when tossed, it has
probability 1/(2k + 1) of falling heads.
If the n coins are tossed, what is the probability that the number of
heads is odd?
Express the answer as a rational function of n.
Source:
Putnam 2001
You don't have to keep track of exactly how many heads, only look back at the k-1 case to compute the k case.
k 1/(2k+1)
1 1/3
even: 2/3
odd: 1/3
2 1/5
even: (2/3)(4/5) + (1/3)(1/5) = 9/15 = 3/5
odd: (2/3)(1/5) + (1/3)(4/5) = 6/15 = 2/5
3 1/7
even: (3/5)(6/7) + (2/5)(1/7) = 20/35 = 4/7
odd: (3/5)(1/7) + (2/5)(6/7) = 15/35 = 3/7
The pattern becomes clear: 1/3, 2/5, 3/7, n/(2n+1)
I'm sure this could be made into a proof using induction.
|
|
Posted by Larry
on 2024-03-05 09:07:44 |
Analytic solution
