A story of a mad old woman and 100 passengers

[hemmul]

Hi all!
This is an interesting problem, on probability, for those who likes solving such things (like me ):

A crowd of 100 passengers is awaiting departure in the airport. As it usually happens, each passenger has his own ticket for a certain place in the plane. As it also sometimes happens, there is an old mad woman ( ) among the passengers, which also has her own ticket. When the voice from the loudspeker, claiming the start of boarding, reaches her ears, she immediately rushes into the plane and takes a random[/color] seat. Other 99 passengers are assumed to be normal, polite people. They enter the plane one by one, and act in the following manner:
if, entered the plane, one sees his real seat (that printed in the ticket) is free - he takes it. If his real place is already busy - he takes any[/color] of currently free seats...
Question:
What is the probability of that the 100th passenger will take his own place (that printed in his ticket)?[/color]

 

[Njorl]

I came up with a 50% chance that his seat was occupied. It was rather involved for coming up with that. Strange. It seemed at the onset that the chance would be much higher that his seat would be unavailable.

I'll hold off on my work until others have had a while to play!

Njorl

 

[hemmul]

I came up with a 50% chance that his seat was occupied.

You got it!

It was rather involved for coming up with that. Strange. It seemed at the onset that the chance would be much higher that his seat would be unavailable.

That's actually the thing that makes this problem interesting. I'm looking forward to seeing your[/color] solution, but really let's give others some time - it's worth solving, isn't it?

 

[suyver]

Originally posted by hemmul
What is the probability of that the 100th passenger will take his own place (that printed in his ticket)?[/color]

That depends very much on how many seats the plane holds (100? 1000? 1 gogoplex?)


Joking aside, I also got 50% (assuming 100 seats in the plane). Surprising!

 

[hemmul]

That depends very much on how many seats the plane holds (100? 1000? 1 gogoplex?)

well, that's true :)
consider:
A Boeing 737 aircraft: 2 engines, 100 seats for passengers (others are removed for technical reasons), 10 crew members includeing a captain/head pilot. The aircraft is currently in Kennedy Intl (KJFK), should be ready at local time 19:10:00 for straightout departure at runway 24L, IFR to Seattle-Tahoma (KSEA), height FL300. Temperature +0.7C at sea level, -0.9C at flight level. Local time is 19:05:01. Altimeter 2992. Fuel tank 77% left 77% right. Current gate 2, terminal 1. Radio communications KJFK tower at 787 MHz, KJFK departure 700 MHz, sqawk 7932.

It's interesting, that in this case, the answer remains 50%

 

[hemmul]

solution

Well, i'll start, posting the solution that seems most beautiful and cute for me. If you want to solve the problem yourself, just don't read the rest of this message...

solution[/color]
Let p(i,n) be the probability of that the seat of the last (n-th) passenger (S) is already busy, after the first i passengers entered the plane.
In this case, we are interested in p(99,100)[/color].

p(1,n)=1/n - the probability of that the mad passenger will take the place of the n-th passenger.

It is clear, from the definition above, that:
Probablity of that S will be busy after i'th passenger's entrance, equals p(i-1,n) + probability of that it is taken by i-th passenger[/color]. The latter equals: p(i-1,n)*1/(n-i+1) because it is the sum of two events: his[/color] place is already busy and from the rest places he will choose S.

So:
p(i,n)=p(i-1,n)+p(i-1,n)/(n - i + 1)=p(i-1,n)[/color]*(n-i+2)/(n-i+1)[/color]

Then:
p(n-1,n)=3/2*4/3*5/4*...*n/(n-1)*1/n =1/2.

So, for any number of passengers the result is 1/2 (and is independent from the vectors of ILS approach to KSEA)[/color]!

P.S. This recursive solution (thatks to rsdn.ru) is short, and effective, but there exist also better ones, which i hope some of you have found, and will share with us :)

 

[Njorl]

I considered each "path" to having the last passengers seat occupied.
These consist of chains of events from 1 to 99 in length. For example,
the length one chain is the old lady sitting directly in that seat. The
length two chain is the old lady sitting in the seat of a passenger who
then sits in the last seat.


(P=probability )
Length one:
P=1/100 (1/100 chance the lady takes last seat) 99x(1/100x1/99)

Length 2:
P=98x(1/100x1/99) There are 98 different ways to enact the two step bump

Length 3:
P=98x97x(1/100x1/99x1/98)=97x(1/100x1/99)

Length n:
P=(100-n)x(1/100x1/99)

So the prob of last seat being occupied=sum [n=1-99] of (100-n)x(1/100x1/99)

Well, sum[n=1-99] of (100-n)=sum[n=1-99] of n=100x99/2

so, sum of all P's =(100x99/2)x(1/100x1/99)=1/2

Njorl