1. 3.12 The birthday problem and those cited in Problems 3.9–3.11 can be described as a special case ofthefollowingmodel.Randomly,youdropn ballsinc compartments such that each ball is dropped independently of the others. It is assumed that c >n. What is the probability pn that at least two balls will drop into the same compartment?

(a) Verify that the probability pn is given by pn = 1− c× (c−1)× ···× (c−n+1)

cn

(b) Prove the approximation formula pn ≈ 1−e−1 2n(n−1)/c

.

for c sufficiently large in comparison with n (use the fact that e−x ≈ 1 − x for x close to 0).

(c) Verify that with a fixed c the value n must be chosen as n ≈1.18√

c in order to get a “50:50” chance of at least two balls dropping into the same compartment.