Fun Problem # 4 (Last)

[LetYouDown]

A line of 100 people are waiting to board a plane. There are 100 seats on the flight. (For convenience, say that the Nth passenger in line has a ticket for the seat number N.)

The first person in line is nuts, and will ignore his seat number, and pick a random seat. All the other people will go to their seat unless it is already taken. If it is taken, they will then find a random free seat to sit in.

What is the probability that the 100th person to board the plane will sit in their assigned seat #100?

[jedi]

[ QUOTE ]
A line of 100 people are waiting to board a plane. There are 100 seats on the flight. (For convenience, say that the Nth passenger in line has a ticket for the seat number N.)

The first person in line is nuts, and will ignore his seat number, and pick a random seat. All the other people will go to their seat unless it is already taken. If it is taken, they will then find a random free seat to sit in.

What is the probability that the 100th person to board the plane will sit in their assigned seat #100?

[/ QUOTE ]

1/100?

[r3vbr]

the probability that the seat will be ocupied is certainly less than 50% imo.. i guess between 60%-80% probability that he'll sit in his own seat

[TomCollins]

I thought its 50%, but I can't remember the logic in it. This is gonna drive me nuts.

[LetYouDown]

[ QUOTE ]
I thought its 50%, but I can't remember the logic in it. This is gonna drive me nuts.

[/ QUOTE ]
My apologies /images/graemlins/grin.gif

[SumZero]

Let X be the number of people in line.

If X=1, P_1=1.

If X=2, P_2=1/2.

If X=3, P_3=1/2. (1/3 of the time first guy chooses seat 1, then 2 chooses 2 and 3 gets his seat. 1/3 of the time 1 chooses 2, then we have X=2 problem where 2 has a 50/50 choice and half the time 3 gets his seat. 1/3 of the time first guy chooses 3 and 3 will not get his seat (he'll get 1 instead). So 1/3 + 1/3 * 1/2 + 0 = 1/2)

If X=4, P_4=1/2. (1/4 of the time the first guy seat 1 and everybody gets their seat. 1/4 of the time the guy chooses seat 2 and now we have a version of the X=3 problem. 1/4 of the time he chooses seat 3 and then 2 chooses his own seat and then we have the X=2 problem again. 1/4 of the time we'll get the first guy choosing the 4th seat and 4 will never get his seat. So 1/4 + 1/4 * 1/2 + 1/4 * 1/2 + 0 = 1/2).

More generally if X=M for M>4 we get:

1/M + 1/M * P_(M-1) + 1/M * P_(M-2) + ... + 1/M * P_3 + 1/M * P_2 + 0 = 1/M * (1 + (M-2)/2) = 1/M * M/2 = 1/2.

[AaronBrown]

SumZero and TomCollins are correct, but there's an easier way to do it.

The game is over as soon as anyone sits in either seat 1 or 100. After that, everyone will get their own seat. It could be the first guy or the 99th guy or anyone in between, but someone has to do it before the 100th guy because there's only one seat left when he gets there.

We know whoever takes one of these seats is picking at random. It's either the first guy, who is insane, or a sane person with a seat number other than 1 or 100. Sane people not sitting in their own seats pick at random.

Therefore, whoever first sits in one of those two seats picked at random, so she was equally likely to pick 1 as 100.

[moomoocow]

Oh wow! This is an incredibly elegant solution. Kudos! I was tearing my hair out trying to figure out how to solve this. Now I can stop and give my poor scalp a break.

Cheers,

[BruceZ]

[ QUOTE ]
A line of 100 people are waiting to board a plane. There are 100 seats on the flight. (For convenience, say that the Nth passenger in line has a ticket for the seat number N.)

The first person in line is nuts, and will ignore his seat number, and pick a random seat. All the other people will go to their seat unless it is already taken. If it is taken, they will then find a random free seat to sit in.

What is the probability that the 100th person to board the plane will sit in their assigned seat #100?

[/ QUOTE ]


Crazy guy picks any seat with probability 1/100. He can take seat 100, or he can take seat 100-N. If he takes 100-N, then guy 100-N will have a choice of N+1 seats, including seat 100, and the crazy guy's original seat 1, and he picks one with probability 1/(N+1). If he chooses seat 1, then seat 100 will be spared for guy 100. If he takes seat 100-n, then guy 100-n will have a choice of n+1 seats, and he picks one with probability 1/(n+1), and so on.

seat 100, P(100 taken) = 1
seat 100-1, P(100 taken) = 1/2*1 = 1/2
seat 100-2, P(100 taken) = 1/3*(1 + 1/2) = 1/2
seat 100-3, P(100 taken) = 1/4*(1 + 1/2 + 1/2) = 1/2
...
seat 1 (crazy guy), P(100 taken) = 1/100*(1 + 1/2*98) = 1/2

All of these probabilities are 1/2, so taking anyone's seat, except 100 or 1, will result in a probability of 1/2 that seat 100 will be taken from that point on.

So the probability that seat 100 will be taken is 1/2.