-----Original Message-----
From: Leonid Bogachev
Sent: Wed 1/30/2008 19:19
To: Suhal Bux; [log in to unmask]
Subject: RE: Airplane riddle
Dear Suhal & allstat,
The answer is 0.5.
The puzzle can be modelled using a Markov chain on the integers 1,...,100,
with transition probabilities as follows:
from state 1 it can jump to any state (including 1) with equal probability:
p(1,i)=1/100 (i=1,...,100);
from state 2 it can jump, with equal probability 1/99, either to state 1
or to any of the subsequent states, 3,...,100:
p(2,i)=1/99 (i=1 or i=3,...,100);
.............
in general, from state k it can jump, with equal probability 1/(100-k+1),
either to state 1 or to any of the subsequent states, k+1,...,100;
............
finally, from state 100, it jumps to state 1 with pobability 1.
The idea behind this Markov chain is to follow the sitting allocations of
"displaced" passengers: the 1st passenger can choose any seat; if he takes
say seat 10 then passengers 2,...,9 will take their own seats, but
passenger 10 will have to go to seat 1 or to any of the remaining seats
11,...,100, etc.
Now, in order that the 100th passenger gets his own seat, all we need is
that our Markov chain hits state 1 prior to state 100. In other words, we
need to find the return probability f_1 (i.e., starting from state 1 to
get back to 1 before getting to state 100). Introducing the similar
probabilities f_k (k=1,...,100), we have a set of difference equations:
f_1=1/100 +(1/100)*(f_2+...+f_100),
f_2=1/99 + (1/99)*(f_3+...+f_100),
f_3=1/98 + (1/98)*(f_4+...+f_100),
........
f_k=1/(100-k+1) + (1/(100-k+1))*(f_{k+1}+...+f_100),
........
f_98=1/3 + (1/3)*(f_99+f_100),
f_99=1/2 + (1/2)*f_100,
f_100=0 (boundary condition).
Solving this system "in the reverse order" we obtain (by induction)
f_99=1/2,
f_98=1/3+(1/3)*(1/2)=1/2,
...
f_k=1/(100-k+1) + (1/(100-k+1))*(100-k-1)*(1/2)=1/2,
...
hence
f_1=1/2, QED.
Given such a simple answer, I don't quite like the solution above, as it
is too technical. There must be a "smart" solution, but knowing the answer
may help find it!
Many thanks for a beautiful puzzle.
Best wishes
Leonid Bogachev
---
Dr Leonid V. Bogachev
Reader in Probability
Department of Statistics Tel. +44 (0)113 3434972
University of Leeds Fax +44 (0)113 3435090
Leeds LS2 9JT bogachev'at'maths.leeds.ac.uk
United Kingdom www.maths.leeds.ac.uk/~bogachev
-----Original Message-----
From: A UK-based worldwide e-mail broadcast system mailing list on behalf
of Suhal Bux
Sent: Wed 1/30/2008 16:23
To: [log in to unmask]
Subject: Airplane riddle
Hello
I know this isn't strictly the right sort of post but it's interesting
and is doing my head in...
100 passengers are queuing to get on a plane.
Each has a ticket with a seat number and they are standing in order.
The first man in the queue is crazy and will sit anywhere at random.
The rest of the passengers will sit in their own seat, unless it is not
available, in which case they will sit in another seat at random.
What is the probability that the 100th passenger sits in his own seat?
I'd appreciate proofs or good reasoning.
The best most correct answer gets a special prize (a McDonald's
voucher!).
Regards
Suhal Bux
This email was sent from:- Nunwood Consulting Ltd. (registered in England
and Wales no. 3135953) whose head office is based at:- 7, Airport West,
Lancaster Way, Yeadon, Leeds, LS19 7ZA.
Tel +44 (0) 845 372 0101
Fax +44 (0) 845 372 0102
Web http://www.nunwood.com
Email [log in to unmask]
|