~~#~~mathtrivia: 100 students are assigned randomly to 5 classes of equal size. What are the chances that two friends get in the same class?— Burt Kaliski Jr. (@modulomathy) August 28, 2012

The chances that two friends get in the same class is 19 out of 99.

If the classes didn’t have to be of equal size — in other words, if each student was just assigned randomly to one of the five classes, with no limit on the number of students per class — then the probability that two friends would get in the same class would be one in five. A pair of students is effectively being given a pair of independent random number between one and five, and the chances that two such random numbers match is one in five.

However, because the classes must be of equal size (20 students each, to reach the total of 100), the chances that two friends (or any two students; whether they’re friends or not doesn’t affect the assignment) get in the same class is slightly *less* than one in five. The reason is simple: If one of the friends is in a particular class, there are only 19 potential seats that the other friend could be assigned to in that class, compared to 20 in each of the other classes. Hence, the probability of 19 out of the total of 99.

In other words, when the total number of occurrences of any given “random” number is limited, two students’ assignments are not independent of one another. If one student gets a particular random number, there are fewer occurrences left for the other one. Each student still individually gets a random number (the chances that a student gets a particular teacher is one in five); but a pair of students doesn’t get a pair of independent random numbers.

One way to understand an answer like this is to look at a smaller version of the problem. Suppose there were just five students, so that each class had just one student. Clearly, in that case, two friends could never be assigned to the same class; there’s only one seat in each. Yet still, each student has a one in five chance of being assigned to any particular class. Or suppose there were 10 students, so that each class had just two. Then there would be a possibility that two friends could be assigned to the same class, but it would be less than the chances that the friend would be assigned to any one of the of other classes.

Moving to an even smaller version, we can write down all the arrangements to make the point. Consider the case instead where there are just four students and two classes. Let A, B, C and D be the students. Then the class arrangements — all equally likely — are as follows:

Class 1 | Class 2 |

AB | CD |

AC | BD |

AD | BC |

BC | AD |

BD | AC |

CD | AB |

The chances that two specified students get in the same class is one in three. Consider the students A and B: only in the first and last of the six arrangements are they in the same class.

If we were to write out all arrangements for the 100 students and five classes (there would be 100! / (20!)^5 such arrangements), we’d find a similar pattern: only a fraction 19/99 of the arrangements would have any specified pair of students in the same class.

There’s a general formula for this kind of problem. If N students are assigned randomly to k classes of size (N/k), then the chances that two friends get in the same class is (N/k)-1 out of N-1.

A happy start to the school year for this year’s students — and may they find friends in all their classes.

Pingback: #math trivia solution: Two friends got in the same class … « modulomathy.com