techInterview Discussion

Problem :- A line of 100 airline passengers is waiting to board a plane. They each hold a ticket to one of the 100 seats on that flight. (For convenience, let's say that the nth passenger in line has a ticket for the seat number n.)
Unfortunately, the first person in line is crazy, and will ignore the seat number on their ticket, picking a random seat to occupy. All of the other passengers are quite normal, and will go to their proper seat unless it is already occupied. If it is occupied, they will then find a free seat to sit in, at random.
What is the probability that the last (100th) person to board the plane will sit in their proper seat (#100)?

Answer :- Hi everyone on the net is saying by induction the ansewer is 1/2 , but i am not able to understand it. It may be my fault and that's why I need your help. Let me explain the problem I am facing. Let me assume that there are 3 persons and what is the probabilty that 3rd person will get his seat given 1st person is crazy.
Now, there are 3! means 6 possibilities (seating arrangements).
123 , 132 , 213, 231 , 312, 321
with 123 and 132 is not possible as Ist person is crazy. Also, 231 is not possible as if 1 seats at 3rd position 2nd is not crazy so it will sit at 2nd position. So only 3 possible sitting arangment are possible.

213, 312 and 321 and out of this favourable is just one which is 213 . So, the probability should be 1/3 in this case.

When I solved for 4 persons probability comes out to be 3/7.
And u can see as the number of persons increases it approaches to 1/2 for n equals to infinite number of people.

Am I right? If not please correct me I will be very thankful.

>Now, there are 3! means 6 possibilities
>(seating arrangements).
>123 , 132 , 213, 231 , 312, 321
>with 123 and 132 is not possible as Ist person is crazy.
>Also, 231 is not possible as if 1 seats at 3rd position
>2nd is not crazy so it will sit at 2nd position. So only
>3 possible sitting arangment are possible.

The first guy is SO crazy he COULD randomly pick his own seat.

So the only ones we can eliminate are 231 and 132, because the second guy would sit in his seat if avaliable.

This leaves 123, 213, 312, 321
Passenger 3 gets his own seat 1/2 the time.

For four passengers, the possiblities are:
(x-ing out the ones that are not possible--because a "normal" passenger would sit in their own seat if it is open)

1234
1243 x
1324 x
1342 x
1423 x
1432 x
2134
2143 x
2314 x
2341 x
2413 x
2431 x
3124
3142 x
3214
3241 x
3412 x
3421 x
4123
4132
4213
4231
4312 x
4321 x

Of the 8 valid possibilities, 1/2 of them have player 4 sitting in the his own seat.

An easier way to think about it:
There are only two (relevant) possible outcomes of a random seat choice:
1) Seat 1  (1/100 chance)
2) Seat 100 (1/100 chance)
3) Some other seat (98/100 chance)

Case 1 - Each other person can sit in their assigned seat, and the last passenger can sit his own. Let's call this a "win"

Case 2 - Each other person can sit in their assigned seat, but the last passenger's seat is taken, and he has to sit in seat 1. Let's call this a "loss"

Case 3 doesn't particularly interest us, because it simply defers the "decision" point to a passenger later, who will make another random choice.

At each point, the chances of randomly choosing seat 1 is the same as randomly choosing seat n, so the chances will always be 1/2, no matter how many seats/passengers we're talking about.