|
The solution to this one is pretty mathimatically involved.
The crazy passenger that boards first has an equal chance of getting on any of the 100 seats. Therefore, the probability of this person sitting in a particular seat k is 1/100.
Now for any value of k, all the passengers up to k will board and take their seats as normal. Then the k-th passenger will find themselves out of a seat, and pick a random seat, in effect, becoming the crazy passenger for a problem with 101 - k passengers.
(For example if the crazy person takes the tenth seat, passengers 2 through 9 will be seated normally, and when passenger 10's turn comes, they can be considered the crazy passenger first in line of 91 people boarding a plane with 91 seats.)
Let us define P(n) as the probability that the last of n passengers boards their proper place under the conditions of the problem. So for solution, we are looking to find the value of P(100).
In a situation with n passengers, the first, "crazy", passenger can take any of the seats 1 .. n with the probability of 1/n. Also, given some seat number k that the crazy passenger may occupy, the problem will become that of 1+n-k passengers.
Therefore, we can say that
P(n) = 1/n * (1 + P(n-1) + P(n-2) + ... + P(2))
(This problem does not make sense with less than 2 passengers. Also, it is easy to see that P(2) is 1/2)
What we would like to do is see what the value of P(n) is in terms of P(n-1).
P(n-1) = 1/(n-1) * (1 + P(n-2) + P(n-3) + ... + P(2)
P(n-1) * (n-1) = (1 + P(n-2) + P(n-3) + ... + P(2)
P(n) = 1/n * (1 + P(n-1) + P(n-2) + ... + P(2))
(P(n) * n) - P(n-1) = (1 + P(n-2) + ... + P(2)) So,
(P(n) * n) - P(n-1) = P(n-1) * (n-1)
(P(n) * n) - P(n-1) = (P(n-1) * n) - P(n-1)
(P(n) * n) = (P(n-1) * n)
P(n) = P(n-1)
This shows us that the problem's answer does not change if we add one more passenger. Starting at 2 passengers with the anser of 1/2, we can add passengers indefinitely, and still arrive at the same answer. Thus for the instance with 100 passengers, the probability of the last one getting to their proper seat is also 1/2, or 50%.
|
