63rd Putnam 2002 Problem B1 An event is a hit or a miss. The first event is a hit, the second is a miss. Thereafter the probability of a hit equals the proportion of hits in the previous trials (so, for example, the probability of a hit in the third trial is 1/2). What is the probability of exactly 50 hits in the first 100 trials? Solution
: 1/99. We start by exploring n trials for small n. For n = 2, we have p(1 hit) = 1. For n = 3, we have p(1 hit) = p(2 hits) = 1/2. For n = 4, we have p(HMHH) = (1/2)(2/3), p(HMHM) = (1/2)(1/3), p(HMMH) = (1/2) (1/3), p(HMMM) = (1/2)(2/3), so p(1 hit) = 1/3, p(2 hits) = 1/3, p(3 hits) = 1/3. For n = 5, we have p(1 hit) = (1/3)(3/4) = 1/4, and p(2 hits) = (1/3)(1/4) + (1/3)(2/4) = 1/4. Similarly, p(3 hits) = (1/3)(2/4) + (1/3)(1/4) = 1/4 and hence p(4 hits) = 1/4. Thus we are led to conjecture that the probability of k hits in n trials is 1/(n-1) for k = 1, 2, ... , n-1. We use induction on n. We have just shown that it is true for n = 2, 3, 4, 5. Suppose it is true for n-1. Then for n, we have p(1 hit) = (1/(n-2) )( (n- 2)/(n-1) ) = 1/(n-1). For k > 1, we have p(k hits) = (1/(n-2) ) ( (n-1-k)/(n-1) + (k-1)/(n-1) ) = 1/(n-1). So the result is true for n. 63rd Putnam 2002 © John Scholes jscholes@kalva.demon.co.uk 11 Dec 2002