## Sunday, April 10, 2011

### There are n buses in a city. Each of them carries at most m passengers. Find the probability that at least two of them carry the same number of passen

There are n buses in a city. Each of them carries at most m passengers. Find the probability that at least two of them carry the same number of passengers.

This is equal to 1-(probability that they all carry different number of passengers). That probability in paranthesis is equal to (m+1)!/((m+1-n)! * (m+1)^n). This is given that (m+1) >= n. If (m+1) < n, then the probability is 1.

- m+1 because maximum m passengers mean m+1 different possiblities (a bus could carry 0 passengers).
- The first bus has (m+1) possibilities in terms of number of passengers. The second has m+1, the third has m+1 and so on. Total number of orderings possible is (m+1) ^ n.
- For the number of passengers to be different in each bus, first bus has m+1 possibilities, second has m, third has m-1 nd so on. For n buses, this is equal to (m+1)!/(m+1-n)!. Dividing this by (m+1)/n gives the possibility. Subtract this number from one to find at least two buses with the same amount of passengers.

Solved by James