Small step of logic or a giant leap of math … take your pick!

October 17th, 2004 admin Posted in Tidbits |

There are a 100 people trying to get onto the same flight you are. The airplane has a 100 seats. You are all ready to board. You are the last one in the line of passengers at the gate. The first guy walks in to the flight and promptly realizes that he does not have his boarding pass on him and does not remember his seat number. So he picks one at random, hoping his charm will take care of the after effects. Every one else takes their assigned seat if it is available. If someone is already sitting on it they quietly look for an empty one and sit there. By the time you get in there is only 1 seat left. What is the probability that the seat which remains is indeed the one originally assigned to you?
This problem, I heard on National Public Radio’s show called Car Talk a couple of weekends back, and immediately set to solving it. I solved it in about 15 minutes with relatively straight forward mathematics, but had the nagging feeling that the problem did not deserve the insight-less fiddling around with drone mathematics, and instead had a much more elegant and insightful, logical solution. I had to wait for the next show for the answer, which as I suspected was crisp and short. The first thing I tried to do was to get to the answer. Once I got there I would decide if I was satisfied by my method or not. This brute-fore technique meant I started with the probability the first guy got his assigned seat. Denoting that by P₁, I concluded,

P₁ = P(first guy picks his assigned seat)

= 1/100

P₂ = P(second person picks his assigned seat)

= p(first person does not pick the second person’s assigned seat)

= 1 - p(first person picks second person’s seat)

= 1 - 1/100

= 99/100

P₃ = p(third person gets his assigned seat)

= p(neither of the first two take his seat)

= 1 - p(either of the first two take his seat)

= 1 - p(first takes third’s seat OR second takes third’s seat)

= 1 - p(first takes third’s seat) - p(second takes third’s seat)

The probability that the first takes third’s seat is 1/100.

The probability that the second takes third’s seat is p(first takes second’s seat and second takes third’s seat), because second would only ever try to sit anywhere other than his assigned seat, if first has already occupied his rightful seat. Therefore this probability becomes p(first takes second’s seat). p(second takes third’s seat). The reason the probabilities get multiplied in the previous line is because the probability of first taking seconds seat is independent of the probability of second taking third’s seat once he decide to choose a random seat. p(first takes second’s seat) = 1/100 and p(second takes third’s seat)= 1/99 since second has 99 seats to choose from when he enters the plane.

continuing our equation from above

= 1 - 1/100 - 1/100.1/99

= 99/100 -1/100.1/99

= (1/100).(99-1/99)

= (1/100).(99.99 - 1)/99

= (1/100). (99 + 1).(99 - 1)/99 using P²-1 = (p+1).(p-1)

= 98/99

If we continue this lengthy procedure and keep our thoughts straight we will see that

P₄ = p(fourth person gets his assigned seat) = 97/98

P₅ = p(fifth person gets his assigned seat) = 96/97 and so on … till we find out

P₁₀₀ = p(100^th person gets his assigned seat) = 1/2

The answer is deceptively simple and has something about it that makes us wonder if this headlong dive into mathematical woods is necessary. An even stronger whiff of suspicion is leant by the seeming irrelevance of the total number of people trying to board the flight. I would have gotten a similar pattern with 50, 80, 200 or 200 million passengers. I felt sure that there was an easier way to figuring this out. I thought for a while, talked about it to a couple of my accommodating friends over lunch, and decided to wait for the answer on NPR’s “Car Talk” show hosted by Click and Clack the Tappet brothers.

Here is their version of the answer, in my words. If someone chooses the seat assigned to the first person then there will be no more need for any seat exchanges. If someone chooses your seat (you are the last one to get on the plane), your probability to get the seat assigned to you is 0. Lets think about the first assertion. If the first person sits by chance on his assigned seat, passengers 2,3,4 … 100 will not notice any problem and will sit on their assigned seat. Say passenger 1 sits on some other seat say number n. The first passenger to note a problem will be passenger assigned seat n. Up until that point all passengers happily seat themselves into their assigned seats. Say passenger assigned to n sits on a seat numbered m, the a similar logic applies and only passenger assigned to m, will notice a problem. If any of these passengers who choose a seat randomly, choose seat originally assigned to passenger 1, no one after them will notice any problem, since the only person who could have noticed a problem is passenger 1 himself who is already seated. Therefore a subset of the total number of passengers will make a decision to choose a seat at random. If they choose the seat assigned to person 1, you are guaranteed to get your seat. If they choose the seat assigned to you, you are guaranteed to not get your seat. To a person choosing a seat at random, your seat is no different that the first person’s seat. So irrespective of the number of people (both total and one’s who have to choose), it’s just a matter of is your seat chosen first or is the first person’s seat chosen first. Therefore due to the symmetry in the argument the answer is 1/2.