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.

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...

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."

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

My math is almost certainly wrong.

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.

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

Then:

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).

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.

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 0...you 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?

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%)

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?

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.

101-that passenger's position. Then the next passenger to board replaces the old lady.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 alln>4,nbeing 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)*[CFTLPISITn-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 forn=6,n=7, up ton=100, plugging the numbers in the formula yields the exact same chance -- 50%.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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

"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."

So the chance she sits in the 100th passenger's seat is only (1/99) x (1/99).

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.

1) Be struck by lightning; or

2) Not.

But that doesn't mean there's a 50% chance of me getting hit by lightning.

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.

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?

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?

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.

Q.E.D.

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.

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.

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.

The expected value of getting your assigned seat is independent of the quantity of seats.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.

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

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?

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.

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

aheadof 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

larry@denenberg.com

http://larry.denenberg.com