On Sep 11, 10:32 am, Karthik Singaram Lakshmanan
<karthiksinga...@gmail.com> wrote:
> 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.
Doesn't matter how many passengers or seats there are,
as long as they are equal and larger than one. There are
only two seats that matter, the first passenger's seat and
the last passenger's seat.
The tricky part is convincing someone that the last boarder
must end up in one of those two seats.
Which means if anyone takes either of those seats, the
last boarder ends up in the other one. Every time someone
makes a random pick, if they pick one of those two seats
the probabilities for either are equal so it's a 50-50, if
they don't pick they just pass the ultimate decision on
to someone later in the line.
--
Geoff
--~--~---------~--~----~------------~-------~--~----~
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
-~----------~----~----~----~------~----~------~--~---
