Probability question about meeting people

analysisprobabilitypuzzlerecreational-mathematics

Here is the problem:

You go to a school that last 3 years, and you start in the first year. You meet one new random person everyday and there are 300 days in the school year.

In every year, there are 200 people (Do not include yourself as one of them), and so every year the people in the highest year leave and 200 newcomers leave.

The question is "What is probability that you will run out people to meet in school before you leave it?"

For example – In the first year you meet the 200 people in your year and 100 in the year above. Then, next year, you meet all 200 people in the new year below you and another 100 from the year above.

In your final year, there are only 200 new people joining the school and you talk to them but you still have 100 days in the year left and so you lost.

However, if you had started with the highest year and talked to them and 100 from the year above, then next year you would talk to the 100 remaining from the year above and the 200 in your year, and in the final year you have 400 people to talk to within 300 days, so you would win with 100 to spare.

Best Answer

In your last year, there are $599$ students other than yourself, and there must be at least $300$ of them that you haven't met, so fewer than $300$ that you have already met. In your first two years, you met $600$ students, and if fewer than $300$ are still in school, more than $300$ must have graduated. Thus, you succeed if and only if, in the first two years, you met more than $300$ of those ahead of you.

Since there are only $200$ students one year ahead of you, you must have met at least $101$ of the graduating seniors. Let $s$ be the number of seniors you met and $j$ be the number of juniors you met, where $j\leq300-s$. Then you met $300-s-j$ members of your own class.

In your second year, there are $j$ students in the class above you and $300-s-j$ student in your own class that you've already met, so $299+s$ strangers. Let $k$ be the number of students from the class ahead of you that you meet this year. We must have $k+j+s\geq301$, so $k\geq301-s-j$ and obviously $k$ is at most $200-j$. There remaining $300-k$ people you meet are chosen from the $299+s-(200-j)=99+s+j$ strangers who aren't one year ahead of you.

The probability of success is

$$\sum_{s=101}^{200}\sum_{j=0}^{300-s}\sum_{k=301-s-j}^{200-j}\frac{\binom{200}{s}\binom{200}{j}\binom{199}{300-s-j}}{\binom{599}{300}}\frac{\binom{200-j}{k}\binom{99+s+j}{300-k}}{\binom{299+s}{300}}$$

I wrote a python script to evaluate this.

from math import factorial

def choose(n,m):
    if m > n:
        return 0
    return factorial(n)//(factorial(m)*factorial(n-m))

choices = choose(599, 300)

prob = sum(choose(200,s)*choose(200,j)*choose(199,300-s-j)/choices*\
           choose(200-j,k)*choose(99+s+j,300-k)/choose(299+s,300)\
           for s in range(101,201) for j in range(301-s) for k in range(301-s-j,201-j))
print(prob)

The script output

4.296291459801449e-06

so if I haven't made any mistakes, the probability is a little less than $4.3\cdot10^{-6}$.

Related Question