[Puzzleblogger Kevan Choset, August 30, 2005 at 12:15pm] Trackbacks
The Old Woman and the Airplane:

There is an airplane with 100 seats, and there are 100 passengers each of whom has an assigned seat on the plane. The passengers line up in a random order to get on the plane. The first woman on line is a confused old lady who doesn't know how to find her proper seat. She just sits in a random seat. When each person after her gets on the plane, they look to see if their assigned seat is available. If it is, they sit in it. If it is not (i.e., if the old lady or someone else before them has sat in it), they sit in a random seat. What are the odds that the 100th person sits in his/her proper assigned seat?

There are two very different ways to do this. The brute force long equation way, and the cute, sneaky, but simple way. Hopefully we'll get both on here.

Lou Wainwright (mail):
It's always 50/50.
8.30.2005 1:27pm
Kristian (mail) (www):
Hmm... Statistics...yuck

Gut feeling, he walks onto to the plane with 1 seat left, there is a 1% chance it is his. But I am pretty sure sure it is is actually higher. Why? the 1% is also the chance chance that the woman sits in her chair. But there is also the chance that, for example, #2 could sit in the confused woman's chair, thus allowing the rest fof the poeple to sit in their chairs.

So Passenger 1 ahs a 1% chance to sit in her chair, but passenger 2 has a very high chance to sit in his, and so on... It would be a degenerative case where each person bumped another...
8.30.2005 1:31pm
Why did the first woman start by connecting to the internet?
8.30.2005 1:31pm
Kevan Choset (mail):
A surefire way for telling if someone is from Long Island is that we say "wait on line" for what you do outside movie theaters, while the rest of the country says "wait in line."
8.30.2005 1:34pm
A. Nonymous (mail):
I think the answer has something to do with the color of the hats they are wearing, right?
8.30.2005 1:35pm
Paul Virkler (mail):
chances of first passenger taking right seat 1/100
second passenger 99/100 x 1/99= 1/100
3rd passenger 98/100 x 1/98 = 1/100
Last passenger would have 99% chance of getting right seat
8.30.2005 1:37pm
cka3n (mail) (www):
I think this puzzle could alternatively be phrased as what are the odds that, if 99 people pick from 100 seats completely at random, the last seat available is the seat assigned ex ante to the 100th person. After 1 person, the odds of that last seat being available are 99/100. After 2 people, the odds are 99/100*98/99. After three people, the odds are 99/100*98/99*98/98. Etc. That ends up being 99!/100!, which reduces to 1/100.

My math is almost certainly wrong.
8.30.2005 1:38pm
Lou Wainwright (mail):
Oh, you want to know why. :) Here's how I did it. Start with less seats.

2 Seats -> Obviously a 50% chance of getting my seat.

3 Seats [Old Lady, Random Guy, Me] 3 Possible Outcomes:
a.) She sits in her seat, so a 100% chance of me getting in mine.
b.) She sits in the RG seat. Now he's got a 50/50 chance of sitting in mine. So 50% for me.
c.) She sits in my seat. 0% chance of me sitting in mine.

So with 3 seats the chance is: 1/3*100% + 1/3*50% + 1/3*0% = 50%

4 seats [OL, RG1, RG2, Me]: 4 Possible Outcomes
a.) She sits in her seat (100% for Me)
b.) She sits in RG1's seat. Now, he has to choose a seat at random, but if he sits in the Old Lady's assigned seat they two of them have swapped, and everyone else is good. I.e. we have now got the same situation as we had above with three seats. One seat that is 'right' and two seats that are 'wrong'. We know from above that this situation results in there being a 50% chance of me getting my seat.
c.) She sits in RG2's seat. Now RG1 will go to his, and RG2 has to make a 50/50 choice. This is the same as the 2 seat situation above and obviously there is a 50% chance of me ending up in the right seat.
d.) She sits in my seat. 0% chance for me.

So with 4 seats: 1/4*100% + 1/4*50% + 1/4*50% + 1/4*0% = 50%.

As you can see any number of seats reduces to the same situation. There is always a 50/50 chance of ending up in your assigned seat. I look forward to someone explaining this with less words.
8.30.2005 1:41pm
alkali (mail) (www):
The following may be helpful.

Consider 3 seats, and let '123' be the result where everyone gets the right seat. (1 is the old lady, 3 the last passenger.)


1xx -- 1/3 chance, always leads to 123
x1x -- 1/3 chance, which leads either to 213 or 312 (1/6 chance of each)
xx1 -- 1/3 chance, always leads to 321

Hence the chance of the 3rd person getting the right seat is 1/2 (that is, 1/3 chance of 123 plus 1/6 chance of 213).
8.30.2005 1:44pm
cka3n (mail) (www):
And now I wish I could take that back, as I misread the problem.

If the nth passenger picks randomly, the seat was not the 100th passengers seat. In that case, there is one less seat to be concerned with (the old lady's seat). if the nth passenger picks their own seat, there is one less seat to be concerned with. At the end, there is a 1/2 chance that the 100th passenger will end up in the right seat.
8.30.2005 1:44pm
OneEyedMan (mail) (www):
Okay, here is a simplifying idea. Whatever seat the lady sits in, the problem simplifies to a plane with 100-that passenger's position.
8.30.2005 1:48pm
Eric Courtney (mail):
99% Given that the problem of mis-assigned seats ends the moment someone sits in the old women's seat (even if it's the old women herself by chance). The only way last boarder sits in a seat other than his/her own is if they are left with the old women's seat.
8.30.2005 1:48pm
JustinS (mail):
Its 50 percent...

There are 3 possible cases of what the old lady may do. There is a 1% chance she gets in her own seat from the start, which means there is a 100% chance the 100th passagner will get in his own seat. There is a 1% chance she will get in the 100th passanger seat, which means the 100th passanger has a 0% chance of getting in his seat.

For the other 98 cases where the old lady gets into a seat other than her own or the 100th passanger, the question is what is the probability that no other subsequent person, when he discovers his seat is occupied, chooses the 100th passanger seat and random. Again, there is a 1/99 change he chooses the old lady's seat (then ending the switching chain, gauranteeing the 100th passanger his seat) and a 1/99 chance he will choose the 100th passanger's seat, therefor making the probability see how there is an iterative process starting here. There is always a 1/X that the probability will be be 1, a 1/X chance the probability will be 0, and a X-2/X chance that will be dependent on 1/X-1. This eventually goes down to there being 2 seats left, with the 100th passanger's seat open and the 99th passanger having a 50% probability of choosing the right seat.

So, iterating the process means that there is a 50% probability the 100th passanger gets into his correct seat.

Am I right?
8.30.2005 1:48pm
DBS (mail):
8.30.2005 1:50pm
The Plumber (www):
if the first woman sits in the wrong seat (its not clear), and everybody else sits in assigned seats (which one presumes they will), then the chance that the last passenger will sit it his/her assigned seat is zero.

If the random seat the confused woman sits in happens to be her assigned seat (luckily), and everybody else sits in their assigned seats, the the last will also sit in their assigned seat (100%)
8.30.2005 1:51pm
DBS (mail):
(1/100 x 0%) [she sits in last person's seat] + (1/100 x 100%) [she sits in her seat, randomly] + (98/100 * (1/98 x 0 + 97/98 * (1/97 * 0 + 96/97 * (.... + 1/2 (100%)))))))...) [same calculation, nested - terms cancel to 1/100]
8.30.2005 1:53pm
Your logic doesn't quite work, what if lady sits in 3d guy's seat and second guy sits in old lady's seat. Where does 3d guy go?
8.30.2005 1:54pm
Second one on helps the lady find her seat.
8.30.2005 1:55pm
Kevan Choset (mail):
The correct answer, which a few people have offered, is 50%. But I've yet to see a convincing proof, either a rigorous mathematical one or the one with a cute shortcut.

The pattern in Lou's comment (here) can lead to the rigorous approach, but you'll need to formalize it more than simply saying the pattern continues.
8.30.2005 1:56pm
OneEyedMan (mail) (www):
I need to change what I said. whatever seat the lady sits in (other than her assigned one or seat 100), the problem simplifies to a plane with 101-that passenger's position. Then the next passenger to board replaces the old lady.
8.30.2005 1:56pm
Matthew Prins (mail) (www):
Let's use a bit of modified induction:

Lou has proved that for n=2,3,4 that the chance of the last person getting into the final seat is 50%. Thus, for all n>4, n being a integer of course, the chance becomes:

(1/n)*[chance for the last passenger if she's in the nth passenger's seat]+(1/n)*[CFTLPISIT n-1th passenger's seat)+...+(1/n)*[CFTLPISIT 1st passenger's seat, i.e. her own]

I don't feel like using real induction, but it's easy to show that for n=5, the last passenger's chance is 1/5*0+1/5*50%+1/5*50%+1/5*50%+1/5*1=50%, and similarly for n=6, n=7, up to n=100, plugging the numbers in the formula yields the exact same chance -- 50%.
8.30.2005 2:00pm
Matthew Prins (mail) (www):
Last 50% for n=5 should be 100%, since if she sits in her own seat, he's sure to get his own -- I just mistyped. Logic still holds, however.
8.30.2005 2:02pm
cka3n (mail) (www):
Kevan: Why not my poorly worded proof, that every additional person removes one seat that is not the 100th person's seat from the calculation? I.e., when a new person gets on, if their seat is available, they take it, and so that seat is one less seat to be concerned about. If their seat is not available, then someone must be sitting in their seat, and so that seat is one less seat to be concerned about. After 99 people have gotten on board, you have only two seats to be concerned about, hence 50/50.
8.30.2005 2:03pm
zaoem (mail):
The following two events have equal probability:

1) the old woman' seat is taken before Passenger 100's seat

2) passenger 100's seat is taken before the old woman's seat.

If 1 occurs, P100 is 100% sure to get his set. If 2 occurs P100 has 0% probability of getting his seat. Given that the events are equally likely, there is a 50% chance of P100 landing in his seat.
8.30.2005 2:04pm
Matthew Prins (mail) (www):
[Sigh.] I meant my 1 in the formula should be 100%. You understand, though.
8.30.2005 2:05pm
Matthew Prins (mail) (www):
I assume zaoem's way was the easy way. That's pretty snazzy, dude.
8.30.2005 2:07pm
It's 50%.

Not sure if someone's already hit on this explanation, but: the problem is resolved when one of the bumped passengers sits either in the 100th person's seat or in the 1st person's seat. Since each bumped passenger chooses a seat randomly, each has an equal chance of choosing each of the two "terminal" seats.
8.30.2005 2:10pm
Kevan Choset (mail):
Zaoem, that works for me, unless anyone has an objection. I have another version, which amounts to the same thing:

We know the 100th person can only sit in his own seat or the old lady's seat. Why? Because if the 100th person sits in Joe's seat, that means Joe's seat was available the entire time. Which means Joe's seat was available when Joe came on. Which means Joe would have sat in Joe's seat. So it wouldn't be available for the 100th person anymore.

So there are only two possible seats the 100th person can end up in.

Can someone offer an explanation as to why those two scenarios (he sits in his own seat or he sits in the old lady's seat) are equally likely? The best way I can think of is to resort back to Zeoem's explanation about the order in which they're taken.
8.30.2005 2:11pm

If the old lady sits in the 3rd guy's seat, the 2nd guy will sit in his own. There would be no reason for him to sit anywhere else.
8.30.2005 2:13pm
Here are the proofs that the correct answer is 50%:
1. (cute shortcut). Model this process as a decision tree with 100 steps, with step i representing the decision of the ith person to sit down. At step i, there are two ways the process can terminate -- either the ith person sits in seat 100, guaranteeing person 100 is out of luck, or the ith person sits in the lady's seat, guaranteeing that people (i+1) thru 100 all get the correct seats. If the ith person makes any other choice, we have to continue down the tree to another decision.

All we care about are the stopping points where we learn person 100's fate. Note that at each step, no matter what has happened before, there is always an equal chance of stopping with 100 in the right seat and of stopping with 100 in the wrong seat. Thus, there is a 50%-50% chance -- the # of ways to get person 100 in the right seat always equals the # of ways to guarantee person 100 gets the wrong seat.

2. We can also write out the equation. Let n=100 be the number of passengers. We know the 100th passenger will get to sit in the correct seat if and only if his/her seat is left open through the 99 previous rounds. Thus, the odds the old lady takes his seat are 1/n=1/100. The odds the second person takes seat 100 are 1/(n-1)*(n-2)/n -- if the old lady chose seat 100 (1/n) or her own seat (1/n) then the second person will take his own seat, and if he has to pick a new seat, he has 1/(n-1) chance of picking seat 100.

Continuing this analysis, we get the total chance of passenger 100 getting the right seat as:
1/n + 1/(n-1)*(n-2)/n + 1/(n-2)*(n-3)/(n-1)*(n-2)/n
+ 1/(n-3) * (n-4)/(n-2)*(n-3)/(n-1)*(n-2)/n) ...
= 1/n + (n-2)/n(n-1) + (n-3)/n(n-1) + (n-4)/n(n-1) + ... 1/n(n-1) [by cancelling like terms]
= [(n-1) + (n-2) + (n-3) + ... + 1]/(n(n-1))
= [1/2 * n(n-1)] / n(n-1) [by taking the sum of the arithmetic series in brackets]
= 1/2.
8.30.2005 2:15pm
JustinS (mail):
I think the formula is Prob(X) = 1/X + (X-2)/X * Prob(X-1) for all X > 1.
8.30.2005 2:17pm
Preferred Customer (mail):
I don't do math, but even I can figure out that there's a 50 percent shot of me sitting the in my assigned seat.

If I am the hundredth person, when I get on the plane there is one seat left. Either it is mine, or it isn't.
8.30.2005 2:28pm
Note that zaoem's statement is correct but not a proof. There is a 99% chance that Person #2's seat is taken before the old woman's seat and a 98.1% chance that Person #3's seat is taken before the old woman's. So yes, there is a 50% chance that seat 100 is taken before the old woman's, but it is not obvious why that is so without more math.
8.30.2005 2:34pm
Noah Snyder (mail):
On Kevan's question of why the two possibilities (passenger100 sits in his own seat or the old woman's seat) are equally likely, the way I would explain that is:

Let's suppose that passenger100 is the old husband. Just lake the old woman he can't tell the difference between any seats.

This problem is completely equivalent to the original because the 100th person doesn't have any choice anyway, so it doesn't matter if he can distinguish his own seat or not.

However, in the new version it's more clear why the two scenarios are equally likely:

None of the passengers can tell the difference between those two seats!

The old woman and her husband can't tell any seats apart, so they can't distinguish their own seats. All of the other passengers can only distinguish their own seat from all the other ones. Thus, *no one* can tell the difference between the two seats in question.

The situation is symmetric under replacing the woman's seat with the husband's seat. So the probabilities *must* be equal.

Symmetry rocks.
8.30.2005 2:45pm
zaoem (mail):
"So yes, there is a 50% chance that seat 100 is taken before the old woman's, but it is not obvious why that is so without more math."

It is obvious because there is no characteristic in the set-up of the game that provides persons 1-99 with a higher/lower probability of taking seat 100 than taking the old woman's seat.
8.30.2005 2:48pm
Sasha (mail):
The correct result has already appeared above, but here's a way of thinking about the problem that I like (though it's not the simplest).

Suppose N-1 people have already boarded. The assigned seats of People 2 through N-1 are already occupied (not necessarily by their assigned occupants). Now rename those people so their number corresponds to their seat: i.e., the person in Seat 2 is now labeled Person 2. One person is sitting outside of those seats, either in Seat 1 or elsewhere. Rename that person into Old Lady. (In this way, every time a new person comes in and finds his place occupied, he becomes the new Old Lady.) This renaming doesn't change where anyone's sitting, so it doesn't affect any probabilities for anyone coming in later.

Remember that Old Lady is sitting in one of 102-N seats: either in Seat 1 or somewhere between seats N and 100. The conditional probability that she's sitting in any one of those seats, given that she isn't in seats 2 through N, is 1/(102-N). Therefore, when the next guy, person N, comes in, the probability that Old Lady is in his seat is 1/(102-N). When N=100, that probability is 1/2.
8.30.2005 2:50pm
The correct answer is 0%. While the 100th passenger is waiting to sit down, the flight attendant tells everyone "Eenie, meenie, miney, moe. Take a seat, we've got to go". The 100th passenger, who is easily offended at such rhymes, immediately dashes off the plane in search of his lawyer...
8.30.2005 3:03pm
zaoem: "obvious because" means that something was not obvious.
Your second statement is an adequate explanation, but your initial answer -- stating that it is obvious the two probabilities are equal -- is essentially just assuming the final answer.
8.30.2005 3:26pm
Lou Wainwright (mail):
Although identical, I find that Clint's phrasing is the clearest 'short form' answer above. I had to think to understand Zaoem's and Kevin's but Clint's produced a simple "Ahhhhhh". If I had to explain it to someone else I'd now say:

"There are only two seats that matter, Mine and the Old Lady's. If someone sits in her's first, I will get my seat. If mine is sat in first, I won't. Since to everyone boarding the plane there is no difference between those two seats there is an 50% chance of either seat being sat in first."
8.30.2005 3:27pm
What if the Old Lady gets up midway through the exercise because she realizes that she's seated herself in an exit row and does not feel, upon reflection, that she is capable of performing the tasks associated with that seat?
8.30.2005 3:34pm
What the heck? This is the reason I went to law school, to avoid all this math and thinking. If wanted to think and do math and not hire experts to do it for me, I would have gone to medical school. ;-)
8.30.2005 3:37pm
Paul Virkler (mail):
The 50-50 logic is wrong. If old lady sits in wrong seat the next passenger will sit in right seat 98 out of 99 times. If she sits in wrong seat there is only a one in 99 chance that it will be the 100th passenger's seat.
So the chance she sits in the 100th passenger's seat is only (1/99) x (1/99).
8.30.2005 5:31pm
Dave! (mail) (www):
New problem: How many lawyers does it take to solve a simple probability problem? :)
8.30.2005 5:31pm
Alexandra von Maltzan (mail) (www):
When the 100th passenger arrives, the seat is either:

1) his pre-asigned seat or
2) someone else (including the old lady) is sitting in it

Therefore it's a 1/2 or 50-50 chance the seat is his pre-asigned.
8.30.2005 5:43pm
Rywill (mail):
Just because there are two possible outcomes doesn't mean the chance of either is 50%. On the way home from work today, I will either:

1) Be struck by lightning; or
2) Not.

But that doesn't mean there's a 50% chance of me getting hit by lightning.
8.30.2005 5:56pm
Nuts, Rywill, I was just going to propose that the people using that logic buy a $100 million Lotto ticket from me for $50 mill.
8.30.2005 6:00pm
John Armstrong (mail):
It's 50/50, and here's the sneaky (mathematician's) way:

Basically, this problem constructs a random cycle starting at 1 (the old lady's seat) and ending with the number of the person who ends up randomly picking her seat. Further, the order of the seats in the cycle is always increasing, thus if 100 is involved in the cycle it's always the last one and the last person must take seat 1. So, if we compose any cycle like this with the swap of 1 and 100, it will give another valid cycle, and further this composition swaps cycles involving 100 and cycles that don't, in pairs. Thus there are as many cycles involving 100 as there are that don't, and thus the probability is 1/2.
8.30.2005 6:29pm
Greg Hamer:
By Sasha's example, the problem is equivalent to everytime someone encounters the old lady in their seat, they make her get up and pick another seat, which she does randomly. This will occaisionally keep happening until she picks her seat or the 100th persons seat, which are equally likely.
8.30.2005 6:33pm
uh clem (mail):
the problem is equivalent to everytime someone encounters the old lady in their seat, they make her get up and pick another seat, which she does randomly.

This is probably the best simplifying explanation so far. Bravo.

If the problem had been stated this way in the first place it would have been much easier to solve - of course that's what makes it a puzzle isn't it?
8.30.2005 6:45pm
Sasha (mail):
I like Greg Hamer's rephrasing -- it's the same as my way, but clearer because it doesn't require relabeling.
8.30.2005 6:45pm
byrd (mail):
I'm not big on math, but simple logic tells me the chances of the last person sitting in the correct seat is 1/100 = 1%. Because that is the chance the old lady sat in the correct seat at the beginning.

We can simply forget about the other 98 people because, if she is sitting in the right seat, then they're all sitting in the right seat. If she's sitting in the wrong seat, they all will sit somewhere and when the last person gets on there will be one seat left. It will be his/hers if the old lady is sitting in the right seat, and not his/hers if the old lady is not sitting in the right seat. No?
8.30.2005 7:12pm
byrd (mail):
Never mind my last post. I have no clue how to figure these things out. But it looks like I'm not alone here.
8.30.2005 7:16pm
Tristan (mail) (www):
A proof by induction for a generalized number of seats n, n>1.

In the initial case, n=2. The answer here is trivially 1/2.

Now, if you have any number of seats n, n>2, assume that for all N, n>N>1, the answer is 1/2.

There are three cases: the old lady sits in the nth seat (p=1/n) and so person n does not, the old lady sits in her own seat (p=1/n) and everyone sits as assigned, and the old lady sits in some other seat (p=(n-2)/n); without loss of generality, call that seat m. Now, the people in seats 2 through (m-1) sit in their proper places. The mth person randomly sits either in the old lady's seat or one of the n-m other available seats, so this problem is identical to one in which there were n-m+1 seats to begin with - just treat the mth person as the old lady. Since we know that n>m>1, we also know that n>n-m+1>1; therefore if the old lady sits in seat m then the probability of person n sitting in seat n is identical to the probility of person n-m+1 sitting in seat n-m+1 in a model with n-m+1 seats, which we have assumed is 1/2. Since this is true for any value of m, the probability is 1/2 for the entire case.

So the probability of the nth person sitting in the nth seat is (1/n)*0+(1/n)*1+((n-2)/n)*1/2= (2+n-2)/2n= 1/2.

8.30.2005 7:46pm
Kevan Choset (mail):
Greg Hamer -- great solution.
8.30.2005 8:07pm
Franco (mail):

I also like Greg's phrasing. Another effort at the same thing:

Suppose the old lady is confused b/c the last passenger to board accidentally took 2 seat assignments. When the last passenger enters, seats 2-99 are known to be occupied b/c passengers 2-99 had an opportunity to take their own seat if still free. There's only 1 seat left, either #1 or #100. Just before the last passenger gets on, he notices he has 2 assignments (one of which must match the last available seat) and returns one to the flight attendant at random.
8.30.2005 9:01pm
Sasha (mail):
Tristan -- To be even more general: What's the probability that, with T total seats, person N (any number above 1) gets to sit in his seat? Just repeat my previous proof, with the Greg Hamer rephrasing:

Replace the problem with one where, if someone finds his seat occupied by the Old Lady, he makes the Old Lady find a new seat. Because all people, if they choose a seat randomly, do so by the same process, this doesn't change any probabilities of a seat's being occupied.

Now suppose N-1 people have already boarded. The assigned seats of People 2 through N-1 are already occupied. Old Lady is sitting in one of T+2-N seats: either in Seat 1 or somewhere between seats N and T. The conditional probability that she's sitting in any one of those seats, given that she isn't in seats 2 through N, is 1/(T+2-N). That's also the probability that Old Lady is in the seat of the next guy, person N.

When N=T -- that is, whenever the last guy comes on -- that probability is 1/2. When N=2, it's 1/T -- that's the probability that the second guy finds his seat.
8.30.2005 9:17pm
Bleepless (mail):
P100 complains to stewardess, who politely asks P1 to move. She does, requiring the P in her seat to move. This keeps up for a while until the passengers get very angry. The Department of Homeland Security is called. Everybody is arrested. They get seats in cells, then all hire Alan Dershowitz and have the joy of seeing their names in his next book, as soon as they serve their sentences.
8.31.2005 12:14am
Patrick McKenzie (mail):
You already have the correct answer but here is another way to look at it:

There are three classes of seats on the airplane: Old Lady's, Mine, and Ones We Don't Care About. We've got 100 passengers to seat, and for the moment they're sitting randomly. The randomness ends when someone sits in the Old Lady's Seat, where we know everything will work out fine after that and I get my seat at the end, or someone sits in my seat, where we know I'm screwed no matter what happens. Randomness continues as long as people continue to sit in the Don't Care seats. Given that out of the universe of Old Lady's and Mine, each is equally likely, 50% of the outcomes lead to me sitting in the right seat.
8.31.2005 1:38am
lee piazza (mail):
Now can we shoot anyone who is wearing a red hat and sitting in the wrong seat?
8.31.2005 1:50am
Jack Johnson (mail):

"I look forward to someone explaining this with less words."

The expected value of getting your assigned seat is independent of the quantity of seats.
8.31.2005 2:40am
Well I'd certainly ask her to move if she was in my seat, or takes hers if it looked better!
8.31.2005 5:52am
Windypundit (www):
For every passenger after the old lady, the following is true when they board: (a) Their assigned seat is already taken, so they sit elsewhere, or (b) their assigned seat is available and they take it. Either way, once a passenger sits down, his assigned seat is guaranteed to be filled, by himself or someone else. The old lady is the only exception.

So when the last passenger boards, only his seat or the old lady's seat can be available: The logic of the previous paragraph guarantees that the assigned seats of all other passengers are already filled.

Every passenger that does not sit in their own seat has chosen another seat at random, including the old lady. The last passenger's seat and the old lady's seat are equally likely to have been filled by this random process. The odds of the last passenger getting the assigned seat are therefore 50/50.
8.31.2005 12:39pm
chris (mail):
Long way formal proof I haven't seen above. Let f(n) be the probability of last person finding seat in n person problem.

f(2) = 1/2

f(n) = (1/n) + (1/n) f(n-1) + (1/n) f(n-2) ... (1/n) f(2)

This second equation comes from the following. If old lady sits in own seat, last person sits in own seat. If old lady sits in person m's seat, persons 1 through m-1 sit in their own seat, person m becomes the old lady in an n-m person problem.

For any fixed n, the equations f(2),...,f(n) are a system of n-1 linear equations
with n-1 unknowns, thus there is at most one solution. Propose f(n-m) = 1/2 for all m. This is verified by f(n-m) = (1/(n-m)) + ((n-m-2)/(n-m)) (1/2) = 1/2. QED
8.31.2005 6:45pm
Bill Woods (mail):
Greg Hamer: By Sasha's example, the problem is equivalent to everytime someone encounters the old lady in their seat, they make her get up and pick another seat, which she does randomly. This will occaisionally keep happening until she picks her seat or the 100th persons seat, which are equally likely.

The trouble with this formulation is that the 100th passenger then has a 100% chance of winding up in his proper seat. Why should he behave differently than any of passengers 2–99 who found the Old Lady occupying the wrong seat?
9.1.2005 4:10am
old maltese:
Bill: it's because *you* are the 100th passenger and *she* has become the 99th passenger. As such, she had 2 seats to choose between, so she had a 50/50 chance of sitting in *your* seat, meaning that you have a 50/50 chance of its still being available.

But we can make it 100%: a kind passenger finding the Old Lady in his seat would say, of course, 'Ma'am, let me show you to your seat.' After which, no more problems.
9.1.2005 11:49am
Larry Denenberg (mail) (www):
Let's try an even more general case.

Suppose there are any number of old ladies scattered anywhere in the line, and that you yourself are located anywhere in the line. Then the probability that you get your own seat is j/(j+k), where k is the number of old ladies ahead of you in the line, and j is the number of people in the line counting from you to the end (that is, there are j-1 people after you in line). The total number of people in line is irrelevant, as is the number of old ladies after you in line (if any), as is the exact distribution of the old ladies.

Note that in the original problem we have j=k=1, giving 1/2 as it should.

There's an easy proof (available here) by induction over the number of people in front of you. But there's a simple way to see it: Suppose the line consists just of k old ladies, then you, then j-1 other people (old ladies or not). There are j+k seats total. What happens? k seats are taken at random and then it's your turn. Obviously you get your seat with probability j/(j+k). And putting any number of non-old-ladies anywhere before you in line makes no difference, since taking any non-old-lady's seat has the effect of transforming that person into an old lady.

/Larry Denenberg
9.1.2005 1:13pm