Thank you for the link, I had a look at it. However, I cannot help wondering if the solution described there is complete, because there is this tricky assumption that 'no preference has been exhibited by the boarding passengers towards either of the two seats'. The event that the first seat is left out may occur in one of, say, x ways, and similarly the event that the last seat is left out may occur in one of y ways. The solution seems to assume that - a) x=y, and b) the probability of the union of events in the first category is equal to the probability of the union of events in the second. I would have normally thought that these things are not trivial, and it is important to prove them. Of course, I may be wrong, it's just that I would like to be sure. Much of my article seems to spend time proving the stated assumption, so I just thought I would mention my doubts.

Thank you again for taking the time with the problem.

They have no idea which seat is which. They do have a preference to taking their own seat of course. They can also identify their own seat. They can't distinguish between the seats of the first and the last passengers.

I found your writing style clear and easy to follow. Your method is sound and I agree with your conclusions, including the extensions of the problem you mention. There are a couple of possible improvements I'd like to suggest:

1) It'seems clear to me that there is one central insight or trick that makes your whole method of analysis go forward, and that is the idea of showing that there is a one to one correspondence between the sets of cases where the last passenger does or does not get his own seat. However, in order to make this work, you have to set up some technical apparatus, e.g. words, sets of words, operations of swapping letters of the words, etc. This can obscure the intuitive idea; to some extent this is unavoidable. To overcome this trouble, it is good to state in intuitive terms first, exactly what the technical trick is, then set up the apparatus, mentioning as you go along how each part fits into your main insight. This will assist readers in following along. Otherwise, they must figure out what the main insight is by looking at the apparatus you have set up and trying to infer its purpose. It is true that you tell the reader what you are doing when come to the one to one mapping, but I would suggest that you outline this idea earlier, so that the reader never has to worry about the point of the technical apparatus as it is set up.

2) Know your audience. I suspect that more people are familiar with basic probability than with the idea of words and their mappings, so for at least some people, the original problem will be more understandable than your solution. If you are confident that your target audience knows the techniques you use in your analysis, then there is no problem here.

3) It is sometimes more illuminating (and more fun) to present more than one analysis of the problem, each of which highlights different aspects of it, and then to show how the different analyses interconnect. (See below.)

Now, on to your comments about Alex's solution.

I think Alex's solution was somewhat terse, so I'll fill in the details and generalize it. First, to paraphrase your normalizing assumptions, passengers enter one at a time, take a seat, and stay in it. There are two classes of passengers: obedient passengers always find and take their assigned seat if it is available, otherwise they take a random seat with equal probability of taking any empty seat; random passengers take a random set when they board, with equal probability of taking any empty seat.

Now suppose that there are n seats, r random passengers, and n-r obedient passengers. The most important thing to notice is that once an obedient passenger has boarded the plane, his assigned seat is guaranteed to be filled, because either it was already filled, or he takes it. Therefore, when the k+1st passenger is ready to board, all seats assigned to obedient passengers numbered k or less are guaranteed to be filled.

It is crucial to notice that in this problem, we do not care who is sitting in each of these seats. The only question is about which seats are available when the k+1st passenger is ready to board. In every possible case, the seats of obedient passengers numbered k or less are filled, therefore we can simply ignore these seats and the passengers in them. When we do this, what is left? There are n-k+r_k seats with r_k passengers filling some of them. Here, r_k is the number of random passengers numbered k or less.

Who are these r_k passengers? Some of them may be random passengers and some may be obedient passengers, but if any of them are obedient passengers, they cannot be sitting in their assigned seats, because these are already filled. Therefore they have chosen seats at random, just as the random passengers have done. Since each of these passengers chooses a random seat with equal probability of choosing any seat, the probability of each seat being filled is the same, hence it is r_k/(n-k+r_k). Therefore, the chance that the k+1st passenger finds his seat empty when he boards is (n-k)/(n-k+r_k).
In the special case r=1, n=100, k=99, we get a probability of 1/2.

You can connect this to your word-based approach by noting that deleting the seats that are guaranteed to be filled is the same as mapping your words to shorter words that do not contain these seats as letters. The shorter words now contain only letters referring to seats that were filled at random, and from this you can calculate the same probability as I got.

--Stuart Anderson

"lign up" ?