I think the answer is 1 out of 5. As in you have a one in five chance of randomly picking the right answer. Then again, send in 5 postcards each with a different answer, and your chances go to 1 out of 1! After all, your goal is to win $25 worth of useless Car Talk junk, right? 
I approached it “from each end”, as bitwise did. We will make two “bins” of probability: the bin into which we put winning events, and the bin into which we put losing events. A winning event is one where someone with a choice (whose seat is taken or whose ticket is lost) sits in a seat that gives everyone else their assigned seats. A losing event is where someone sits in your seat.
For person #1, the probability of a winning event and a losing event are equal, but each is far overshadowed by the probability of passing the choice to some other passenger. The next passenger who gets to choose is one of only 50 passengers (long term average) left. He also has to choose: he can take the seat of the first passenger or your seat (equal probabilities), or he can pass the buck (roughly 25 times more likely than both) by sitting in someone else’s seat.
He sits in someone else’s seat. The winning bin and losing bin are each filled equally! Passengers 75, 88, 92, 94, 97, 98, and 99 are each asked to choose a seat because of previously shuffled passengers, but in each case, they have equal chances of causing a win or a loss, and in all cases except the last two, larger chances of simply “shrinking” the problem.
Nice work, Xema. Exactly how I would have done it myslef, if only I were a little smarter.
Guys, this is all a lot easier than any of you are making it.
The chance is 50%.
Anyone who boards the plane to find their seat occupied has as much chance of filling the first passenger’s seat as he has of filling yours.
If he fills yours, you dont get the seat. If he fills the first passenger’s seat, literally everyone who follows will get their correct seats.
The answer is 1/2.
I, like many others here, came fairly quickly to the conclusion that the answer was 1/100. Personally, I used this reasoning: For n numbers, there are n! possible ways to arrange them. Of those n! possibilities, (n-1)! will have n in the last position (or any other position you care to choose). Therefore the possibility of my sitting in my own seat is (n-1)!/n! = 1/n = 1/100, for n=100.
However, this theory is flawed. It is valid only if all seats are chosen at random. In our example, they are not necessarily random, because if any one person’s seat is available, he must choose that seat instead of taking a random one. This causes many of the possible outcomes to be invalid.
Consider the case for n=5. There are n!=120 possible arrangements. However, in (n-1)!=24 of those, passenger 1 randomly chooses his own seat. If he chooses his own seat, then seat 2 is available for passenger 2, so he must take it. Seat 3 is then available for passenger 3, and so on. So of the 24 possible arrangements where Passenger 1 (P1) chooses Seat 1 (S1), only one combination is “valid” for this example. The other 23 are not possible. So right off the mark we have reduced the number of possible arrangements from 120 to 97.
Then consider the cases where P1 sits in S3, S4, or S5. There are 72 of them. But these cases leave S2 available for P2. He must then sit in S2. So all of the cases which have P2 sitting in S1, S3, S4, or S5 are invalid. This eliminates another 54 cases, pringing our total possible arrangements down to 43.
There are a number of other “invalid” seat arrangements as well. Consider the following:
21345
21354
21435
21453
21534
21543
These are all of the possible arrangements in which P1 takes S2 and P2 takes S1. In these cases, S3 is available, so P3 must take it. Then P4 takes S4 and P5 takes S5, eliminating all but one of the combinations.
Similarly, combinations 25134 and 45132 are invalid: in the first, S4 was available for P4, so he should have taken it; in the second S3 was available for P3.
Once you eliminate all of the invalid combinations for n=5, the original 120 possible combinations is reduced to 16 valid combinations, 8 of which result in Passenger 5 sitting in Seat 5. Having done the calculations by brute force for n=1 to 6, I have shown that the number of valid combinations is 2^(n-1), and that the number of thise which have n in the final position is [2^(n-1)]/2, so the odds are {[2^(n-1)/2]/2(^n-1)} = 1/2. I tried to come up with a formula to prove this result for any n, but alas, my math skills have deteriorated in the years since graduation. (I do actually have a BA in Mathematics, which is probably why I spent so much time and paper working on this.) Hopefully some other Doper can fill in the blanks for me.
Of course, we all missed the most concise (and eloquent) solution to the problem, which goes something like this:
When I get on the plane, there is one seat available.
Either the availible seat is the one that was assigned to me, or it is not.
The odds on it being my assigned seat are therefore 1/2.
QED
This argument is invalid. The fact that there are two possible outcomes does not imply that their probabilities are split evenly, 50/50.
Even though the probability does seem to be 1/2, this is bad reasoning. If you change the problem such that all 100 people choose completely randomly, then you can still say “when I get on the plane, there is one seat available, and it is either the one that was assigned to me or it is not” but that doesn’t mean those two outcomes are equally likely.
I’d agree. That would be like saying your odds of winning the lottery are 50/50, you have either won or you haven’t.
Ayup. That kinda shoots holes in Xema’s solution too.
The probability is 1/2. Below is a proof by strong induction. For the non-mathy types, this probably won’t be convincing, but take my word for it, this is an air tight mathematical fact.
Proof by strong induction:
Clearly, when there are two passengers the probability of sitting in the right seat (success) is ½ because the first passenger has equal chance of choosing his own seat or yours.
Now for strong induction we assume that there is a ½ probability of success for 2, 3, 4, … n passengers and use this to show that this implies that the probability is ½ for n + 1 passengers.
With n + 1 passengers, there is a 1/(n + 1) chance of success right off the bat if the first passenger chooses his own seat. There is also a 1/(n + 1) chance that this passenger will choose your seat. This leaves an (n-1)/(n+1) chance that the first passenger will choose the seat of passenger x. All passengers 2, 3, … x-1 will then sit in their assigned seats. After this there are n+2-x passengers and seats left. Since n+2-x is a member of {2, 3, 4, … n} we can treat the vacant seat number like the occupied passenger x’s seat and due to the induction hypothesis, we now know that chance of success in this situation is ½.
Now we can calculate the total chance of success:
1/(n+1) + [(n-1)/(n+1)]1/2 = 2/(2(n+1)) + (n-1)/(2*(n+1)) = (n+1)/ (2*(n+1)) = ½.
Here’s something that might be interesting.
I’ve verified that for n = 1, 2, 3, 4, 5 there are 2[sup]n - 1[/sup] possible outcomes for this scenario. I’m conjecturing that this pattern holds for any greater value of n.
Even in looking at the trees for the values I’ve examined, I’ve started to see isomorphic subtrees showing up. I don’t have enough information to state the patterns I’m seeing yet, but it might be interesting to explore.
The .5 answer is looking good…I think. :smack: Here’s how I worked it out.
For simplicity, we’ll call the first passenger Mr 1, and his seat will be Seat 1. Mr 100 will assigned Seat 100.
Let’s take a “best case” scenario: the Mr 1 happens to choose Seat 1. Then all others will take their proper seats and Mr 100 will be assured of taking Seat 100.
Take a “second best” case scenario: Mr 1 happens to take the Seat 99. That means that everybody gets to sit in their own seat except Mr 99, who gets to choose either the Seat 1 or Seat 100. Mr 100 gets whatever seat Mr 99 doesn’t take. (It will be either Seat 100 or Seat 1.)
OK. Take a “worst case” scenario: Mr 1 happens takes Seat 2, and Mr 2 happens to take Seat 3, Mr 3 happens to take Seat 4, etc . It doesn’t have to occur serially like that; the point is no one along the way happens to choose their seat randomly. In this scenario, Mr 100 holder will not get Seat 100.
Ok, start from the beginning. Let’s say that the same plane has to be boarded 100 times. There are 100 false alarms that there is a bomber on the plane and the plane must be disembarqued and reboarded and the same fuckwit drops his ticket each and every single time! If we assume statistically that each scenario will be played out with each boarding then Mr 1 will take “worst case” scenario once, the second worst case once , the best case scenario once, the second best case scenario once, fulfilling all the case scenarios, then in 50% of the boardings, Mr 100 will get his seat.
I.e., the answer is .5
QED?
Interesting problem and I’ve read all the answers. So we’ve seen arguments based on conditional probabilities, symmetry, induction, computer simulations, and paper cut-outs. I think that by far the easiest solution comes from a clever insight by Padeye. As Padeye pointed out, the part in the problem that stated “every other passenger [after the first passenger] will take either his assigned seat or, if that seat is taken, that passenger will take any seat at random” is equivalent to “every other passenger [after the first passenger] will take either his assigned seat, or, if that seat is taken, ask the passenger in his assigned seat to move to another randomly selected seat.” With this, it’s easy to see that if Passenger #1 sits in a seat that is not his or yours, he’ll just be asked to get up to find another random seat possibly up to the time before your board. He will then be in either your seat or in another seat, so the probability in this case is 1/2 that your seat is available. So writing this down with probabilities, it goes as follows: Let E = you find your seat empty when you board as the last passenger, S1 = Passenger 1 sits in his own seat when he boards, S2 = Passenger 1 sits in your seat when he boards, S3 = Passenger 1 sits in a seat that is not his or yours when he boards. Then:
P(E) = P(E|S1)P(S1) + P(E|S2)P(S2) + P(E|S3)P(S3)
= (1)(1/100) + (0)(1/100) + (1/2)(98/100)
= 1/2.
The general answer for n passengers is:
P(E) = (1)(1/n) + (0)(1/n) + (1/2)((n-2)/(n))
= 1/2.
Lance Turbo had a great induction proof.
I question this. My argument isn’t “There are two possible outcomes, therefore they must be equally likely.” (This clearly is not necessarily so, as the example of buying a lottery ticket shows.)
Using terminology as before, my argument says that if someone happens to sit in seat Y while F is unoccupied, the last seat remaining will be F. And if someone happens to sit in F first, the last seat remaining will be Y. There are two possibilities, and they are symmetrical - under the terms of the problem, there is no way one can be preferred over the other. It follows that the chance of either outcome is 1 in 2.
And I think jawdirk should get credit for being the first to come up with this. He presented his solution as a protected “spoiler”, and I didn’t see it earlier.
I would like to give props to EsotericEnigma for stating the solution in a way that a non-mathematician like me could intuitively understand. (not intending to take anything away from all the other explanations – I’m just sayin’…)
Sorry, that last bit of my post was meant in jest. I should have made sure that was understood. (I should have used a 
, but I really try not to use smilies.) But the rest of my argument is valid; although it does not qualify as a “proof” I believe it is a strong case of “reasoning by induction”, and I do stand by the result.
The answer is 1/2.
Yeah, I think you’re right. I tend to get a little jumpy when it looks like someone is applying the principle of indifference (“all outcomes must be equally likely because there’s no other reason to assume otherwise”).
I think it was interesting to see the various approaches tried to solve this problem. It is interesting to me that the person who probably has the most mathematical sophistication had more trouble with the problem than some other people. I think that is because is easier to understand if you start in the middle: The 1/n choice of the first person seems to complicate the analysis.
I started with an empirical approach with a deck of cards, and it soon becomes clear that with the choice of answers given, the pick is 1/2.
Xema, jawdirk and others have mostly said what I am going to say, I’ll just be adding a bit.
Assume Mr. Clumsy (1st boarder) did not (P(1/n)) select his own seat, nor your seat. He picked bumpee1’s seat. Everything goes fine till bumpee1 find’s her seat taken. At that point there are two seats of interest, Your seat Y, and Mr. Clumsy’s seat. If bumpee1 picks Y, you lose, if C, you win, as there will be one pair of people in swapped seats. If bumpee1 picks any other seat, she creates bumpee2. Bumpee2 has the same choice. If bumpee2 picks C, he closes a chain of 3 people each of who has shifted one seat. In this case everybody else loads fine, and you win. If he picks Y, you lose. Any other choice again just reduces the problem by 1. We know by enumeration that the game is 50/50 for plane size of 2.
Now since large plane sizes seem to have a p(1/2) and plane sizes of 2,3,4 can be brute forces solved to be 1/2, wouldn’t it be strange if some slightly larger sizes had Prob’s different than 1/2 that converged to 1/2? This of course is not a mathematical proof. I wonder if I slander physicist’s by calling it a “physicist’s proof”? Maybe “naive empiricist’s proof”?
But the only thing needed to turn it into a full proof is to handle the initial assumption the Mr. C took neither your seat, nor his own. True, there is a 1/n chance he will pick Y and make you lose on the first move, but there is an equal chance he will pick his own seat. Each point (Y, C, (other n-2 seats)) in the choice space is equally likely (P Y | point is in subset (y,c)) is (1/2); similarly p(C |…) and prob(you win | Mr. C picks some other point than (y or c)) = 1/2.
Cleaning up a bit
pr(you get your seat) = Prob(W| Mr. C picks his own) * P© + Prob(W | Mr. C picks yours) *p(y) + p(W | some other) * p (other)
1 * (1/n) + 0 * (1/n) + (n-2)/n * P(W with n-1) people =
in all cases except when n = 3, in which case the formula is
1* (1/3) + 0 * (1/3) + prob(that seat 2 person picks your seat | Mr. C did not) which is 1/6, so prob for size 3 is 1/3 + 0 + 1/6 which is also 1/2.
1/n + ((n-2)/n * (1/2)) = 1/2.
(1+0) = (1/2 + 1/2), so substitute , get 1/2 * (1/n)
there is an initial chance that Mr. C will chose Y, making you lose right away. However, this is exactly balanced by the 1/n chance Mr. C will chose his own seat.
Looks kind of familiar.
sorry nivlac. I guess the whole of what I added is the words “swap” and “cycle” for the little they do.