100 passengers board a plane with 100 seats; the first, a crazy old lady, takes a wrong seat, and each...

Many solutions have been posted to this problem.  The majority give a
probability of 50/99 and the next most popular solution seems to be
0.99 or thereabouts.  I agree with the first answer.  It also has been
suggested that a better statement of the problem would be to have the
old lady choose her seat at random rather than insist on sitting in one
of the wrong ones.

let the passengers be designated p1, p2, etc. and the seats to which
they are assigned s1, s2, etc.  The old lady, the first to be seated,
is p1.  These are verbal abbreviations.

let d(n) represent the probability that the n'th passenger will be
"displaced," that is, he will not, or will not be able to sit in his
assigned seat.  We won't give a value to d(1) [Editor: "p(1)" in the
original] for the time being.  Let there be m seats on the plane.

p2 is displaced if p1 sits in s2, so that d(2) = d(1)/(m-1).

p3 is displaced if p1 sits in s3 or if p2 is displaced and sits in s3:

  d(3) = d(1)/(m-1) + d(2)/(m-1)

p4 is displaced if p1 sits in s4 or if p2 is displaced and sits in s4
or it p3 is displaced and sits in s4:

  d(4) = d(1)/(m-1) + d(2)/(m-1) + d(3)/(m-2).

If we carry on we soon notice that the first terms are repeats of what
was written for the previous d, and that we may write:

  d(n) = d(n-1)(m-n+3)/(m-n+2) for d(3) and higher.

Now would be a good time to assign values to d(1).  If the old lady
always sits in the wrong seat d(1) = 1 and

  d(n) = m/[(m-1)(m-n+2)].

If the old lady chooses a seat at random d(1) = (m-1)/m since there are
m-1 ways she can sit in the wrong seat.  In that case:

  d(n) = 1/(m-n+2).

Indeed, this is a more elegant way to state the problem, for if m = n,
then the last passenger is displaced with probability 1/2 independently
of the number of seats on the plane.

Of the postings I read, only one author worked out the problem in
exactly this way.  Naturally we see eye-to-eye.  Many others got the
"right" answer with radically different logic.  Were they smart, or
were they just lucky?

-- samba@juno.com

There were at least four correct approaches.

However, by far the most elegant solution came from one poster who
observed (I paraphrase):

Consider the correct seat of the passenger who will come in last.  At
various stages, a passenger may come in and find his seat taken.  With
equal probability, he will then sit in the old lady's correct seat (and
then everyone else will get the correct seat), or else that of the
passenger who will come in last.  And thus the probability is 50%.  The
slight change from 50/100 to 50/99 comes about because the old lady may
have sat in the last passenger's seat, increasing slightly the
probability that he gets the wrong one.

This must, I feel, become the 'official' solution, but the others are
still valid.

-- Gerry Quinn <gerryq@indigo.ie>

> What are some of the other "correct" approaches?

My original approach was to write the formula for the last passenger
getting the wrong seat, as the chance that it will not happen that some
previous passenger will (first) not have a seat, and (second) then take
the old lady's seat.  If there are N seats left, there is 1/N chance
for each passenger that his seat is taken, and if so there is 1/N
chance that he then takes the old lady's.  So the chance that this
doesn't happen is 1-1/N^2.  The chance that is never happens to any
passenger between the second and the 99th is:

P = (1 - 1/99^2)(1-1/98^2)(...)(1-1/2^2)

This is simply expanded:

= (99^2-1)(98^2-1)...(2^2-1) / (99^2)(98^2)...(2^2)

= (100.98)(99.97)...(3.1) / (99.99.98.98....2.2)

= 100! 98! / 2! 99! 99!

= 100 / 198

= 50 / 99

-- Gerry Quinn <gerryq@indigo.ie>