You have a set of n biased coins. The mth coin has probability 1/(2m+1) of landing heads (m = 1, 2, ... , n) and the results for each coin are independent. What is the probability that if each coin is tossed once, you get an odd number of heads?
Consider the expansion of (2/3 - 1/3)(4/5 - 1/5)(6/7 - 1/7) ... (2n/((2n+1) - 1/(2n+1)). The negative terms correspond to an odd number of heads. So the product is just prob even - prob odd. But the product telescopes down to 1/(2n+1). Obviously prob even + prob odd = 1, so prob odd = (1 - 1/(2n+1))/2 = n/(2n+1).
62nd Putnam 2001
© John Scholes
16 Dec 2001