Seat permutation problem?

Question

Let n be a natural number greater than 1, and suppose we have n people boarding a train carriage that has n seats, each passenger having a ticket which designates the seat in which they are supposed to sit. The first person to board sits in a seat randomly chosen. From then on, a passenger sits in their designated seat if it's available, and if not, sits in a seat they choose at random.

What is the probability that the nth person sits in the seat designated by their ticket? To win the points, provide a proof.

Answer 1

For the case of n=2, clearly the probability is 1/2 when the 1st person randomly chosen his own seat.
For the case of n, two cases:
when 1st person chose his own seat, prob is 1/n
when 1st person chose any seat other than his nor the last person's seat and the (n-k+1)th person of the remaining (n-k+1) people, where the kth person's seat was chosen by the 1st person, sits in his seat.

Let P(n) be the probability that the nth person sits on his seat.
Thus,
P(n) = 1/n + (n-2)/n * (P(n-k+1))

Try out some cases of n:
For the case of n=3,
P(3) = 1/3 + 1/3 * P(3-2+1), k can only be 2
= 1/3 + 1/3 * P(2)
= 1/3 + 1/3 * 1/2
= 1/2

For the case of n=4,
P(4) = 1/4 + 1/4 * (P(4-2+1) + P(4-3+1)), k = 2 or 3
= 1/4 + 1/4 * (P(3) + P(2))
= 1/4 + 1/4 * 1
= 1/2

For the case of n=5,
P(5) = 1/5 + 1/5 * (P(5-2+1) + P(5-3+1) + P(5-4+1)), k = 2 or 3 or 4
= 1/5 + 1/5 * (P(4) + P(3) + P(2))
= 1/5 + 1/5 * (3/2)
= 1/2

Suspect can prove by induction.
Assume P(2) = P(3) = ... = P(k) = 1/2
P(k+1) = 1/(k+1) + 1/(k+1) * (P(2) + P(3) + ... + P(k))
= 1/(k+1) + 1/(k+1) * ((k-1) * 1/2)
= 1/(k+1) + (k-1)/2(k+1)
= (2+ k-1)/2(k+1)
= (k+1)/2(k+1)
= 1/2

Thus, by induction, P(n) = 1/2 for all n > 1.

Answer 2

It may seem counterintuitive but the probability is 50%.

Let's arbitrarily assume that the passengers were given tickets for seats 1 through N, in that order. It doesn't really affect the problem, but it makes it clearer what's happening.

Now the only seats that end up mattering are seat 1 and seat N. If seat 1 (first passenger's seat) ever gets filled, then all passengers after that will be able to find their seats. This is because there is nobody displaced once seat 1 is filled. In the end passenger N will be able to sit in his seat.

On the other hand, if seat N ever gets filled, then there is no possibility that N will get his seat.

When someone sits in their designated seat, nothing changes. But each time someone is displaced, they will either pick a seat that doesn't matter (i.e. just displaces someone else), or they have an even chance of picking seat 1 (guaranteeing N sits in his seat) or seat N (guaranteeing N doesn't sit in his seat).

Since the choice of seat 1 is equally likely as the choice of seat N, the outcomes happen with even probability.

50% of the time N will be guaranteed to get his seat (if seat 1 is filled first) and 50% of the time N will be unable to sit in his seat (if seat N is filled first).

P(nth person sits in the seat designated by their ticket) = 50%

If it helps to enumerate an example, think of the case of 3 seats.
1 takes seat 1, 2 takes 2, 3 takes 3 --> success
1 takes seat 2, 2 takes 1, 3 takes 3 --> success
1 takes seat 2, 2 takes 3, 3 takes 1 --> failure
1 takes seat 3, 2 takes 2, 3 takes 1 --> failure

2 successes out of 4 outcomes = 50%

You can expand this with 4 seats:
1 takes 1, 2 takes 2, 3 takes 3, 4 takes 4 --> success
1 takes 2, 2 takes 1, 3 takes 3, 4 takes 4 --> success
1 takes 2, 2 takes 3, 3 takes 1, 4 takes 4 --> success
1 takes 2, 2 takes 3, 3 takes 4, 4 takes 1 --> failure
1 takes 2, 2 takes 4, 3 takes 3, 4 takes 1 --> failure
1 takes 3, 2 takes 2, 3 takes 1, 4 takes 4 --> success
1 takes 3, 2 takes 2, 3 takes 4, 4 takes 1 --> failure
1 takes 4, 2 takes 2, 3 takes 3, 4 takes 1 --> failure

4 successes in 8 outcomes --> 50%

I won't go further than that, but trust me, the probability is always 50%.

Answer 3

For the "nth person" to be succefull this would mean that all the 1,2 ...(n-1)the persons should NOT have sat on the "nth seat" which is designated for the "nth person".

Thus the probability that we seek
= "No. ways the (n-1) people sit in (n-1) seats" divided by the "total number of ways the n people can sit in n seats".

"No. ways the (n-1) people sit in (n-1) seats " is because the nth seat" is "for the nth person" ( assigned ) while the rest can sit in any of the remaining (n -1) seats. Thus it is equivalent to finding the no. of permutation of the (n-1) people on (n-1) seats and this is = (n-1)!

"total number of ways the n people can sit in n seats" is because if there were "no conditions" in the problem how many seating configurations would have been possible? The answer is = permutations of n people on n available seats= n!

Thus the probability that the nth person sits in the seat designated by their ticket = [ (n-1)! ]/ [n!] = 1/n

Because
n! = n x (n - 1)! and so
[ (n-1)! ]/ [n!] = (n -1)! /[ n x (n - 1)! ] = 1/n

Hope this helped.

:)