Concidences (Diaconis and Mosteller, 1989). See Section 2.3.1 on the birthday problem. Some categories (like birthdays) are equally likely to occur, with c possible values.

(a) Let k be the number of people needed so that the probability of at least one match is 95%. Show k ≈ 2.45√c.

(b) Suppose there are m categories, all of which are independent and take c possible values. Let k be the number of people needed so that the probability of at least one match in any category is 95%. Show k ≈ 2.45 √c/m.

(c) A group of k people is comparing 

(i) Their birthdays, 

(ii) The last two digits on their social security card, and 

(iii) The two-digit ticket number on their movie stubs. 

How big should k be so that there is a 50% chance of at least one match? A 95% chance?