The deal is that if anyone chooses seat 1 then everyone else will go
to their proper places and person 100 will get seat 100
The probability of passenger 1 choosing seat 1 is (1/100)
Say, he chooses seat (a_1) where (1 < a_1 < 100), this also happens
with prob. (1/100)
We can ignore the case where he chooses seat (100) since that implies
that passenger 100 is not going to get his seat anyways
Now, passenger (a_1) can choose seat 1 with probability (1/(100-a_1+1))
Say, he chooses seat (a_2) where (a_1 < a_2 < 100), this also happens
with prob. (1/(100-a_1+1))
We can ignore the case where he chooses seat (100) since that implies
that passenger 100 is not going to get his seat anyways
Now, passenger (a_2) can choose seat 1 with probability (1/(100-a_2+1))
Say, he chooses seat (a_3) where (a_2 < a_3 < 100), this also happens
with prob. (1/(100-a_3+1))
We can ignore the case where he chooses seat (100) since that implies
that passenger 100 is not going to get his seat anyways
This continues....
Say F(x) = (1/(100-x+1)) for convenience
Say Q(x) = F(x) + F(x)*SUM[x < r < 100] Q(r)
Q(x) denotes the probability that either passenger x chooses seat 1 or
one of the passengers coming after him (before passenger 100) chooses
seat 1
The solution to our problem is therefore Q(1)
Q(99) = F(99) = (1/(100-99+1)) = (1/2)
Q(98) = F(98) + F(98)*(Q(99)) = (1/3) + (1/3)*(1/2) = (1/3)*(3/2) = (1/2)
Q(97) = F(97) + F(97)*(Q(98)+Q(99)) = (1/4) + (1/4)*(1/2+1/2) =
(1/4)*(2) = (1/2)
.....
Q(x) = F(x) + F(x)*SUM[x < r < 100] Q(r) =
F(x){1+(100-x-1)/2}=(1/(100-x+1))*(100-x+1)/2 = (1/2)
....
Q(1) = (1/2)
As with most probability problems, I am sure there is a much simpler
(and intuitive) explanation, but I prefer this solution to make sure
that I am not making arbit assumptions.
Cheers,
Karthik
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com
For more options, visit this group at http://groups.google.com/group/algogeeks
-~----------~----~----~----~------~----~------~--~---
