• Rana Basheer

Interesting probability problem – Crazy airplane guy

This problem I found on the following website. I am just restating it below

A line of 100 airline passengers is waiting to board a plane. They each hold a ticket to one of the 100 seats on that flight. (For convenience, let’s say that the nth passenger in line has a ticket for the seat number n.)  Unfortunately, the first person in line is crazy, and will ignore the seat number on their ticket, picking a random seat to occupy. All of the other passengers are quite normal, and will go to their proper seat unless it is already occupied. If it is occupied, they will then find a free seat to sit in, at random.  What is the probability that the last (100th) person to board the plane will sit in their proper seat (#100)?

Their Answer

Now according to the solution provided by the website the answer is 0.5. Their reasoning is that the crazy situation in which people picking random chairs to sit ends when one of the non-crazy passenger who lost his seat picks the crazy first person’s seat. Hence the probability of the 100th person sitting on the right chair is the sum of probability of passenger 2 to 98 picking the first person’s chair

So that comes out according to them as

P(S_{100}=100)=\frac{1}{99}+\frac{1}{99\times 98}+\frac{1}{98\times 97}+\cdots+\frac{1}{2\times 3}=0.5

I feel the above reasoning is flawed. A passenger who lost his seat could pick the crazy first person’s seat but someone before him would have already picked the 100th person’s seat. I don’t think that scenario is taken into account in their reasoning.

My Answer

So in my view the probability can be solved in reverse way as

P(S_{100}=100) = 1 - P(S_{100}\ne 100)

In the above equation the notation

P(S_i = k) \Rightarrow
i^{th}
k^{th}
P(S_i \ne k) \Rightarrow
i^{th}
k^{th}

The probability that the

100^{th}
P(S_{100}\ne 100)=P(S_1\ne 1\bigcap S_1=100)+P(S_2\ne 2\bigcap S_2=100)+P(S_3\ne 3\bigcap S_3=100)+\cdots+P(S_{98}\ne 98\bigcap S_{98}=100)+P(S_{99}\ne 99\bigcap S_{99}=100)

where

P(S_{98}\ne 98\bigcap S_{98}=100) \Rightarrow
98^{th}

Using the reltationship

P(A\bigcap B)=P(A)P(A|B)
P(S_1\ne 1\bigcap S_1=100)=P(S_1\ne 1)P(S_1=100|S_1\ne 1)
P(S_1\ne 1)=1
P(S_1=100|S_1\ne 1)=\frac{1}{99}
P(S_1=100|S_1\ne 1)=\frac{1}{99}

For the

i^{th};i\in\left\{2,3,\cdots,100\right\}
100-(i-1) = 101-i
j\in\left\{i+1,i+2,\cdots,100\right\}
P(S_i=j|S_i\ne i)=\frac{1}{101-i}
P(S_{100}\ne 100)=\frac{1}{99}+\frac{P(S_2\ne 2)}{99} +\frac{P(S_3\ne 3)}{98}+\cdots+\frac{P(S_{98}\ne 98)}{3}+\frac{P(S_{99}\ne 99)}{2}

Similarly

P(S_{99}\ne 99)=\frac{1}{99}+\frac{P(S_2\ne 2)}{99} +\frac{P(S_3\ne 3)}{98}+\cdots+\frac{P(S_{98}\ne 98)}{3}

Therefore,

P(S_{100}\ne 100) = P(S_{99}\ne 99)+\frac{P(S_{99}\ne 99)}{2}=P(S_{99}\ne 99)\frac{3}{2} =P(S_{98}\ne 98)\frac{3}{2}\frac{4}{3}=\frac{3}{2}\frac{4}{3}\cdots\frac{99}{98}\frac{100}{99}P(S_2\ne 2)=50P(S_2\ne 2)=\frac{50}{99}=0.5051

or

P(S_{100}=100)=1=P(S_{100}\ne 100)=0.4949

Expanding the problem to N seats

Now lets expand this problem to a scenario with N seats and the first person as previously is crazy and won’t sit in his chair and will select randomly a chair from 2 to N to sit. What is the probability that the last person gets to sit in his chair.

Using our previous reasoning the probability that

i^{th}
P(S_i\ne i)=P(S_1\ne 1)P(S_1=i|S_1\ne 1)+P(S_2\ne 2)P(S_2=i|S_2\ne 2)+P(S_3\ne 3)P(S_3=i|S_3\ne 3)+\cdots+P(S_{i-2}\ne i-2)P(S_{i-2}=i|S_{i-2}\ne i-2)+P(S_{i-1}\ne i-1)P(S_{i-1}=i|S_{i-1}\ne i-1)

Since the first guy is not going to sit in his chair P(S_1\ne 1)=1$ and then he is going to choose any of the N-1 seats in random with probability given by

P(S_1=i|S_1\ne 1)=\frac{1}{N-1}
j^{th};j\in\left\{2,3,\cdots,N\right\}
i^{th};i\in\left\{j+1,j+2,\cdots,N\right\}
P(S_j=i|S_j\ne j)=\frac{1}{N-(j-1)}=\frac{1}{N+1-j}

Therefore,

P(S_i\ne i)=\frac{1}{N-1}+\frac{P(S_2\ne 2)}{N-1} +\frac{P(S_3\ne 3)}{N-2}+\cdots+\frac{P(S_{i-2}\ne i-2)}{N+3-i}+\frac{P(S_{i-1}\ne i-1)}{N+2-i}

Similarly for the

(i-1)^{th}
P(S_{i-1}\ne i-1)=\frac{1}{N-1}+\frac{P(S_2\ne 2)}{N-1} +\frac{P(S_3\ne 3)}{N-2}+\cdots+\frac{P(S_{i-2}\ne i-2)}{N+3-i}

That means

P(S_i\ne i)=P(S_{i-1}\ne i-1)+\frac{P(S_{i-1}\ne i-1)}{N+2-i}=P(S_{i-1}\ne i-1)\frac{N+3-i}{N+2-i}= \frac{N}{N+2-i}P(S_2\ne 2)=\frac{N}{(N-1)(N+2-i)}

For the last guy the chance of him not sitting in his chair is when

i=N\Rightarrow P(S_N\ne N)=\frac{N}{2(N-1)}
P(S_N=N)=\frac{N-2}{2N-2}

In the limiting case

\lim_{N\rightarrow\infty}P(S_N=N)=\lim_{N\rightarrow\infty}P(S_N\ne N)=0.5

Verification

I always like to verify my answer with a montecarlo simulation. The result for

N\in\{3,4,5,\cdots,50\}

Monte carlo simulation of crazy guy problem

#probability #Puzzle

0 views

Recent Posts

See All