Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
1  
We've seen this one before: math.stackexchange.com/questions/5595/taking-seats-on-a-plane It's a classic! –  Byron Schmuland Jan 1 at 19:36
1  
@ByronSchmuland I am afraid not. Here I am asking for the probability of the last two correct sit not the last correct sit. –  user117432 Jan 1 at 19:39

2 Answers 2

up vote 8 down vote accepted

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.

share|improve this answer
    
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? –  Michael Edenfield Jan 2 at 1:15
    
@MichaelEdenfield You are right. I edited my answer accordingly. –  MoonKnight Jan 2 at 2:05

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}$.

share|improve this answer
    
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. –  dfeuer Jan 1 at 20:09

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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