15
$\begingroup$

A cohort in a school consists of 75 students who study for 6 years. Each year, the students are randomly distributed into 3 classrooms of 25 students each. What is the probability that, after 6 years, each student has at some point been in a classroom with every other student?

More generally: Starting with an edgeless (undirected) graph on cn vertices, a round consists of first randomly partitioning the vertices into c disjoint sets of n vertices each, then adding an edge between every pair of not-yet-joined vertices that lie in the same set. What is the probability that, after y rounds, the result is a complete graph on cn vertices?

I have estimates and solutions to special cases, and it's straightforward to find the probability that a single given student sees all the others, but I don't know how to tackle the question in general. (I do have a very pretty but completely useless expression for the exact answer, which I can supply if there's interest.) In the case c=3, n=25, y=6 it's clear that the answer is "so close to zero that nobody can tell the difference" but I was hoping for a more precise result. Any guidance appreciated.

  • 0
    This feels like a generalization of the coupon collector problem to me, although this observation may not be helpful.2010-10-21
  • 1
    It is a interesting question, but maybe one reason you haven't seen many responses is that it is a little unclear what you are looking for. I mean, you already have estimates, solutions in special cases, and the exact answer but you are hoping for "a more precise result"? Are you looking for bounds to show when the probability is practically zero? Or are you maybe interested in large y values so the probability is guaranteed to exceed 1/2, say?2010-10-23
  • 0
    @Byron I'm sorry to have given the impression that I know more than I do. In fact, I know almost nothing. The special cases I've solved are trivial, e.g. I know the answer for $c=2$ and $n<4$, but not even for $c=2$ with $n$ arbitrary. My estimates are weak or badly justified or both, and, as I said, my expression for the exact answer is useless in practice. Bottom line: I would have given a better picture had I omitted the last paragraph in the original question, and I apologize for the confusion. I will write up my partial results in an answer.2010-10-24
  • 0
    Why can't you just find all the possible states after six years, and count the ones where the students all meet each other?2010-10-28
  • 0
    @Justin: There are probably way too many possible states, with $\sim 10^{33}$ ways to partition the students into three classes.2010-10-28

2 Answers 2