26 September 2015

# Puzzle: Boarding a plane

Last morning, I was having a rather humorous email exchange with some of my friends from my previous job when one of them, Gasan, sent a very interesting puzzle. This is not that simple. What is surprising is his kids got this problem as a homework problem. Also Raj let me know that the answers are all over the internet. So, if you want to exercise your brain, do not Google it up. After you have given it whatever time you want to give, feel free to look up the answer.

Meanwhile, just to show how much fun we had as a team – or rather the team had at my expense, I am going to copy Gasan’s articulation of the problem as is…

A line of 100 airline passengers are waiting to board a plane. They each hold a ticket to one of the 100 seats on the flight. (for some reference, let’s say that the nth passenger in line has a ticket for the seat number n.)
Unfortunately, the first person in line is a crazy bald headed guy named Rajib, and will ignore the seat number on their ticket, picking a random seat to occupy. All the other passengers including Gasan, Chris, Sunjay, even Raj and Karthik 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)?

Posted September 26, 2015 by Rajib Roy in category "Puzzles

1. By Bhushan Krishnan on

Saw your notes. It seems that you have assumed that Rajib Roy will never take his designated seat whereas the problem states that he chooses a seat at random that could be the seat assigned.

2. By Dhananjay Nene on

Yes, Bhushan, that is indeed the assumption i had worked on and incorrectly so on rereading the problem statement /cc Rajib

1. By Dhananjay Nene on

Actually it tends to 0.5 for larger values of n but is never 0.5.

For n = 2 it is 0
For n = 3 it is 0.25 (not entirely sure .. see my error doubt below)

There is something not quite correct with my calculations after it (though I think I know what I’m not factoring in .. too tired to continue at the moment)

But I am certain it is a value that tends to 0.5 as n grows larger but never is actually 0.5

2. By Dhananjay Nene on

Here r my notes as of now .. will figure out later if there still remains a flaw.

For n = 2
P(Pass #1 taking Pass #n’s seat) = 1/(n-1) = 1
P(Pass#n taking his correct seat) = 1 – 1 = 0
For n = 3
P(Pass #1 taking Pass #n’s seat) = 1/(n-1) = 1/2
P(Pass #2 taking Pass #n’s seat) = (1/2 * 1/2) = 1/4
P(Pass#n taking his correct seat) = 1 – 3/4 = 1/4 = 0.25
For n = 4
P(Pass #1 taking Pass #n’s seat) = 1/(n-1) = 1/3
P(Pass #2 taking Pass #n’s seat) = (2/3 * 1/3) = 1/9
P(Pass #3 taking Pass #n’s seat) = (5/9 * 1/2) = 5/18
P(Pass#n taking his correct seat) = 1 – 13/18 = 5/18 = 0.2778
For n = 5
P(Pass #1 taking Pass #n’s seat) = 1/(n-1) = 1/4
P(Pass #2 taking Pass #n’s seat) = (3/4 * 1/4) = 3/16
P(Pass #3 taking Pass #n’s seat) = (9/16 * 1/3) = 3/16
P(Pass #4 taking Pass #n’s seat) = (6/16 * 1/2) = 3/16
P(Pass#n taking his correct seat) = 1 – 13/16 = 5/16 = 0.3125

3. By Dhananjay Nene on

There is something definitely wrong with the above calcs.

Brute force computations suggests the probabilities depending on total number of passengers is as follows:

n = 2: 0.00
n = 3: 0.25
n = 4: 0.33
n = 5: 0.37
n = 6: 0.40
n = 7: 0.42
n = 10: 0.45
n = 25: 0.48
n = 50: 0.49
n = 100: 0.496

I worked out outcomes for n=3 and n=5 and arrived at 0.5 in both cases. Rajib , do share the proper mathematical way of arriving at it , if you have it

1. By Dhananjay Nene on

Bhaskar Bagchi Could you explain how you arrived at 0.5 for n=3 and n=5. I have documented my notes in a comment reply above.

For n=3 , there are 4 possible outcomes of which 2 are favourable wherein passenger 3 gets seat 3.
1. p1=s1 , p2=s2, p3=s3
2. P1=s2 , p2=s1, p3=s3
3. P1=s2 , p2=s3, p3=s1
4. P1=s3 , p2=s2 , p3 =s1
In a similar fashion one can work out 16 possible outcomes for n=5 , of which 8 are favourable wherein passenger 5 gets seat 5.
Rajib has also used mathematical induction nicely to arrive at this by framing a probability function F(n)-ask him for his notes

2. By Rajib Roy on

Dhananjay, here is the one with 3: the 5 will take a little more time to type out:
When G1 comes in, he has three choices – sit in S1 (his seat), S2 or S3 (final guy). If he sits in S1 – which has probability of 1/3, then G2 gets S2 and G3 gets S3. So the final guy getting is seat is 1/3
Now if G1 sits in S2 which has prob 1/3, when G2 comes, he can sit either in S1 or S3. Each has prob 1/2. If he sits in S1, G3 gets his seat. Else, he does not. So the prob that G3 gets his seat is 1/3*1/2 = 1/6.
Finally if G1 sat in S3, G3 obviously does not get his seat.
So, the prob of the last guy getting his seat is 1/3 + 1/6 = 1/2.
Could it be possible that you interpreted the problem differently?

1. By Dhananjay Nene on

Yes that is what happened. As Bhushan correctly figured it out. I had interpreted the first guy to sit in any seat randomly BUT HIS OWN.

And here i’m trying to figure out the mathematical expression to figure out the probability under the modified scenario. Still wasn’t able to solve it correctly but hope to get back to it 🙂 🙂

2. By Rajib Roy on

Should it not be 1/2 minus 1/n? Basically subtract the probability the first guy sits in the first chair

3. By Arne Gustafson on

You forgot a variable. Only certain people can sit in a exit row.

Changes the problem by excluding
Y, number of excluded seats

This site uses Akismet to reduce spam. Learn how your comment data is processed.