Boarding a plane: a mathematical puzzle

I heard of this puzzle from my friend, Luke McShane.

I was lucky to guess the answer correctly, immediately. I would like to see intuitively (which would be clever) but alas it was just lucky. It took me an hour or so to prove the answer, though my proof (given below) is not rigorous.

Boarding a plane

It's amazing what images come up when you google 'boarding a plane'.

Imagine there is a plane with say 100 seats, and on this journey, it is fully booked, with every seat taken. One passenger, the first to get on, has mislaid his seat ticket and decides to just sit anywhere. The second passenger gets on and, if his allotted seat isn't taken, sits in it, but if by chance the first person had sat in the second person's seat, then the second person again just sits somewhere at random. And so does the third, and fourth, and so on. (Quite hard to explain briefly).

What is the chance that the 100th person will sit in his allotted seat?

Solution

It's 50:50.

My logic was 'it can't be 0%, and it can't be 100%, it has to be somewhere in between; it probably doesn't depend on the precise number of seats being 100, and it might converge as the number of gets large, and if it converges, it probably converges to 50%'. This type of logic is called guessing. In fact, there is no convergence, and the answer is the same for n=2 upwards.

My proof, which is similar to mathematical induction, was as follows.

Start with n=2, two seats on the plane. Then it is 50:50 whether the first person sits in his seat or not. Hence it is 50:50 that the second person will.

Now, n=3. There is a 1/3 chance that the first person will sit in his correct seat, and a 2/3 chance that he won't. Take the first case first: he sits in his correct seat. Then we are down to the situation with n=2; in the second case, when the second person joins the plane he finds his seat taken, and sits in one of the two remaining seats: it is 50:50 that he sits in his correct seat.

And so on. It gets harder for n=4 or n=5 (where I stopped) but soon it became clear what the pattern was. For n=4, there is a 1/4 chance that the first person sits in his correct seat, which then means the problem simplifies to the n=3 case; and 3/4 chance he doesn't, when a bit of work is needed to see how it simplifies- but – and I drew diagrams to make it entirely clear, what can be seen is that the case of there being n seats and be simplified either to n-1, where the first person sits in his correct seat, or n-2 when he doesn't…and all cases therefore reduce eventually to the n=2 case.

Posted with Blogsy