Problem 10

You are the last person in a line of 100 people who are boarding an aircraft that has 100 seats. Each person in line has a boarding pass assigning her/him to one of the seats so that every seat is assigned to someone. The first person in line accidentally drops his boarding pass into the ventilating system where it is immediately shredded. Having forgotten his seat assignment, he then chooses a seat at random and sits down. The remaining 99 people board the plane one at a time. Each person takes his/her assigned seat if it is available and if it is not, sits in one of the remaining open seats at random. What is the probability you will end up sitting in your assigned seat?

[Problem submitted by Roger Wolf, LACC Chairman of Mathematics.]

Solution for Problem 10:

Solution 1:

The nature of the problem does not change if we renumber the seats so that the assigned seat number corresponds to the person’s position in line. So the person whose ticket was shredded was assigned seat number 1 and you were assigned seat number 100.

Consider changing the seating process as follows: The person with the shredded ticket, call him Joe, chooses a seat at random. The remaining 99 people board the plane one at a time. Each person takes his/her assigned seat, bumping Joe out of the seat if she/he finds him occupying it. Joe then immediately takes one of the remaining open seats at random. Then the next person in line takes her/his seat, bumping Joe if necessary, thus continuing the process until everyone is seated. It is clear that the probability you do not have to bump Joe from your assigned seat is the same as the probability you get your assigned seat in the original problem.

In the newly posed problem, let be the event that, when you board the plane, Joe has been bumped exactly k times. It is clear that , and that ,,….., are mutually exclusive events such that =1. Let be the event that the Joe never sits in your seat. The solution to the problem is . Clearly for . (When you board the plane, everyone but Joe is in his or her assigned seat. Joe must be in seat #1 or your seat, #100. That means he sat in his present location immediately after being displaced for the time. If he had taken any other seat, it would have resulted in a displacement. The probability he sat in seat #1 given that he chose randomly between seat #1 and seat #100, is .)

Consequently:

====

Solution 2:

Let be the nth guy in line, be the seat assigned to . So is assigned to who lost his boarding pass, and is assigned to , that is you. Let be the event that exactly i persons make a random choice of seats. Given , the last person who makes a random choice of seats must choose his seat from {,}. Therefore given, the probability that you sit in your assigned seat is P(→∣)=1/2.

P(→)=(→∣) = = = .