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 -~----------~----~----~----~------~----~------~--~---