7
$\begingroup$

Here's a nice probability puzzle I have thought about for a class I'm TAing, I'm curious to see different solutions :) It goes like this:

We have a classroom with $n$ seats available and $m \leq n$ incoming students. Each student has an (ordered) list of $k \leq n$ preferences for the seat he is going to take, where $k$ is some fixed positive integer. If at the moment of his arrival, a person's $k$ favorite seats are already taken, then he randomly chooses a seat from the remaining $n-k$. What is the probability that everyone occupies one of his favorite $k$ seats?

$\endgroup$
3
  • $\begingroup$ So, let me check a simple example to see if I understand the problem: if $m = n = 2, k = 1$, what is the answer ? (if they each prefer a different seat, then they are both guaranteed to get a favorite; if they each prefer the same seat, there is no chance they will both get their favorite.) Are you taking the probablity among all such scenarios (for fixed $m,n,k$)? $\endgroup$
    – BaronVT
    Feb 9, 2015 at 21:42
  • 1
    $\begingroup$ Yes, probability among such scenarios (for fixed $m,n,k$); in your case, it is indeed $1/2$. $\endgroup$
    – TJIF
    Feb 9, 2015 at 22:06
  • $\begingroup$ Are the lists completely random ? $\endgroup$
    – mercio
    Feb 12, 2015 at 7:45

1 Answer 1

Reset to default
4
+50
$\begingroup$

The students numbered $1$ to $k$ will always get a seat among their preferences.

For a student number $s$ with $s>k$, the probability that all $k$ of his preferred seats are taken is $\binom k {s-1}/\binom k n$. Because the lists of the next students are random, it doesn't matter which seat is taken, so the order in the list doesn't matter at all. The problem is the same if we pick sets of size $k$.

So the probability that every students seats in a preferred seat is $\prod_{s=k+1}^m \left(1 - \frac{(s-1)!(n-k)!}{(s-k-1)!n!}\right)$

$\endgroup$
1
  • 1
    $\begingroup$ Call your result $f(k,m,n)$. I let Mathematica compute some examples, e.g., $f(3,11,14)={19604295639225\over 54839944911388}$. This suggests that no simplification is possible. $\endgroup$
    – Christian Blatter
    Feb 12, 2015 at 10:16

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .