9
$\begingroup$

100 men are getting on a plane (containing 100 chairs) one by one. Each one has a seat number but the first one forgot his number. So he randomly chooses a chair and sits on it. Others do know their own number. Therefore if their seat is not occupied, they sit on it and otherwise they randomly choose a chair and sit. What is the probability that the last two persons sit on their own chair !?

Edit: As @ByronSchmuland mentioned, a similar but different problem is HERE

$\endgroup$
3
8
$\begingroup$

So if there are $n$ seats, the probability of the last $k$ passenger will take their own seats is $P(n,k)$.

When the first passenger randomly takes his seat, there are three possible situations.

1) he takes his own seats with probability $1/n$

2) he takes the seats belongs to one of the last $k$ passengers with probability $k/n$

3) he takes the seats of the $m$th passenger with probability $1/n$ for each $m$.

In case 1, then every one takes their own seat naturally. In case 2, then it is impossible that last $k$ passengers still take all their seats. In case 3, everyone before $m$th passenger take their seats naturally. the $m$ the passenger have to randomly choose one seat from $n-m+1$ seats and the seat assigned to the first passenger can be viewed as his newly assigned seat. So the probability of the last $k$ passengers takes their own seats is $P(n-m+1,k)$.

In summary $$P(n,k)=\frac{1}{n}+\frac{1}{n}\sum_{m=2}^{n-k} P(n-m+1,k)$$ It is easily transformed to $$ Q(n,k)=\frac{1}{n}\sum_{m=2}^{n-k} Q(n-m+1,k), \quad \text{where } Q(n,k)\equiv P(n,k)-\frac{1}{k+1} $$

For each $k$, it is easy to see that $P(n=k+1,k)=1/(k+1)$. So $Q(n,k)=0$ for any $n\ge k$. So $$P(n\ge k,k)=\frac{1}{k+1}$$

So in your problem, $n=100, k=2$, the answer would be 1/3.

In this similar problem, $n=100, k=1$, the answer would be 1/2.

$\endgroup$
2
  • $\begingroup$ I'm confused how you got the term for case 3, since the "rules" for seating aren't recursive; in particular, if passenger #2 finds his seat empty (passenger #1 did not take it) then #2 will always sit there, so the probability that #2 sits in the correct seat is (n - 1)/n, not 1/(n - 1)... isn't it? $\endgroup$
    – KutuluMike
    Jan 2 '14 at 1:15
  • $\begingroup$ @MichaelEdenfield You are right. I edited my answer accordingly. $\endgroup$
    – MoonKnight
    Jan 2 '14 at 2:05
8
$\begingroup$

Using the idea on the rephrased solution Byron linked in the comments. Assume the first guy keeps getting evicted from his seat. Then there will come a time when the first guy is sent to one of 3 positions. Of these only 1 leaves the 2 last guy's places available so the probability of this happening is $\frac{1}{3}$ and if he does get the correct one then the last two passengers will naturally take their seats correctly. So the probability is $\frac{1}{3}$

In fact you can generalize this to see the probability the last $n$ persons get in their places is $\frac{1}{n+1}$ when $n<m$ where $m$ is the total number of seats. For $n=m$, it is trivially $\frac{1}{n}=\frac{1}{m}$.

$\endgroup$
1
  • $\begingroup$ I think you mean $\frac 1 {n+1}$. Note: all the passengers after the first get the right seats if and only if the first did, which gives the correct $\frac 1 {99+1}=\frac 1{100}$ probability that the first person got the right seat. $\endgroup$
    – dfeuer
    Jan 1 '14 at 20:09

Not the answer you're looking for? Browse other questions tagged or ask your own question.