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

23 COMMENTS :

    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.

      Reply
    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

      Reply
    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

      Reply
    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

      Reply
  1. By Bhaskar Bagchi on

    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

    Reply
    1. By Bhaskar Bagchi on

      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

      Reply
  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?

    Reply
    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 🙂 🙂

      Reply

Leave a Reply

Your email address will not be published.


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