What is the probability that at least 2 professors (out of 100) pick the same course (out of 200)?

Question

Suppose each of 100 professors in a large mathematics department picks at random one of 200 courses. What is the probability that at least two professors pick the same course?

The answer given in 1 - 6.6 x 10^-14. I'm pretty sure you can get this answer by 1-(200!/100! * 1/(200 ^ 100)), but I'm having trouble understanding the basic concepts behind getting the answer.

I don't fully understand why the total possible outcomes would be 200^100 instead of 100^200, if not all courses could possibly be picked by at least one of the professors.

And finally, I don't understand how 200!/100! would be the possible outcomes of no courses being chosen by at least two professors.

Please illuminate me! I'm clearly missing a link.

Answer 1

The total number of ways in which you can assign courses to the professors is $200^{100}$.

The first professor can get any of the 200 courses (200 ways), same for the second (200 ways) and so on. The total number of ways this can happen is thus:

$200 * 200 * 200 ... * 200 (100 times) = 200 ^ {100}$.

Now we want cases where they pick unique courses.

This would be $P(200, 100)$.

Which is nothing but 200 * 199 * ... * 101.

Think about this in this way: you make 200 chits with one course code on each chit, go to Prof. 1, he picks a chit (200 ways), the next Prof. picks a chit (199 ways) and so on.

In the earlier case, each Prof. picks a chit and puts it back in the basket.

P(unique assignment) = $\frac{P(200, 100)}{200^{100}}$.

Thus, required probability = 1 - P(unique assignment)

Answer 2

1- probability that no two professors choose the same course. The number of ways 100 professors choose different courses is $\frac{200!}{100!} = 200 \cdot 199 \ldots 101$

Answer 3

Its the birthday problem in disguise. Just compute the probability of the complement which is that no two professors pick the same course. This means the first professor picks a course with probability 200/200. Second one picks a course with p = 199/200, third one picks a course with p = 198/200 ... and the 100th professor picks a course with p = 101/200. Let A = the event that at least two professors pick the same course Let B = the event that no two professors pick the same course So P(A) = 1 - P(B) = 1 - (200 * 199 * 198 .. 101)(200 ^ 100).

This is likely very close to 1.