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)?
I say 99% chance. My wife says 1% chance. That could be a more dangerous marital puzzle.
100th person is the pilot and has a seat allocated. ☺
I had a guess, which turned out to be correct, but I take no credit for actually working it out.
Its close to 99% but wasn’t able to actually work it out
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.
Yes, Bhushan, that is indeed the assumption i had worked on and incorrectly so on rereading the problem statement /cc Rajib
The real answer, as Steve guessed, is 0.5, Hunt and Dhananjay. Try working it out. It is real fun…
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
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
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
Tagging Karthik, Rajashekar, Chris, Sunjay
Hunt, the lesson is that you meet your wife in the middle and you get it right.
for the other 99, there are only two choices..either their seat is occupied or not.
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
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
Bhaskar, check your inbox
Got it. Thanks !
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?
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 🙂 🙂
Should it not be 1/2 minus 1/n? Basically subtract the probability the first guy sits in the first chair
That could be / likely to be so, but building up so from first principles likely to take an as yet uninvested effort 🙂
You forgot a variable. Only certain people can sit in a exit row.
Changes the problem by excluding
Y, number of excluded seats