Mark Davidson
United Kingdom Armagh

Quote: There’s an airplane with 100 seats, and there are 100 ticketed passengers each with an assigned seat. They line up to board in some random order. However, the first person to board is the worst person alive, and just sits in a random seat, without even looking at his boarding pass. Each subsequent passenger sits in his or her own assigned seat if it’s empty, but sits in a random open seat if the assigned seat is occupied. What is the probability that you, the hundredth passenger to board, finds your seat unoccupied?
http://fivethirtyeight.com/features/willsomeonebesitting...

¡dn ʇǝƃ ʇ,uɐɔ ı puɐ uǝllɐɟ ǝʌ,ı
Canada Chestermere Alberta
Life lesson: Hamsters are NOT diswasher safe.
There are 10 types of people those who understand binary, and those who don't.

You beat me to it by seconds.
Here's the text from that site:
There’s an airplane with 100 seats, and there are 100 ticketed passengers each with an assigned seat. They line up to board in some random order. However, the first person to board is the worst person alive, and just sits in a random seat, without even looking at his boarding pass. Each subsequent passenger sits in his or her own assigned seat if it’s empty, but sits in a random open seat if the assigned seat is occupied. What is the probability that you, the hundredth passenger to board, finds your seat unoccupied?

Mark Davidson
United Kingdom Armagh

I think the solution is:
Spoiler (click to reveal) 50%
I'll hold out on posting my workings until later.



markdavo wrote: I think the solution is: Spoiler (click to reveal) 50% I'll hold out on posting my workings until later.
Your workings:
Spoiler (click to reveal) 50%, it's either taken or it isn't
Seriously though, instinct first of all said simply 1%.
But then, is the answer something like 1/[99!] [!=factorial]?
That wasn't meant to be a stab at the answer, but just to see if I'm in the right ballpark

Mark Davidson
United Kingdom Armagh

Spoiler (click to reveal) Hint: Think about the scenario that someone picks the first passenger's seat at random



markdavo wrote: Spoiler (click to reveal) Hint: Think about the scenario that someone picks the first passenger's seat at random
Spoiler (click to reveal) So it's something like: second passenger = 99% chance his seat is empty third passenger = 98% chance, but also factor in the 1% from the second passenger? fourth = 97%, but also factor in the 1% and 2% chance from the last two. Does that mean it's the sum of 199, plus the same again [from working backwards?]



My take:
Spoiler (click to reveal) Take:
f_N to be the probability of the last passenger's seat being empty in a plane that seats N people.
So the first passenger is going to randomly take someone's seat with each seat having probability of 1/N.
If he picks his own seat, the last seat will be empty
Otherwise say he takes the passenger who is ith counting from the back of the line. All of the passengers up to that passenger will sit in their normal seat, and now we are in a situation with i passengers left and the first one randomly picking a seat, i.e. f_i. So this implies (for N >= 2)
f_N = (1/N) * (1 + f_2 + f_3 + ... + f_{N1} )
or
N f_N = 1 + f_2 + f_3 + f_4 + ... + f_{N2} + f_{N1}
Now look at the case for a plane with N1 passengers
(N  1) f_{N1} = 1 + f_2 + f_3 + ... + f_{N2}
Combining these two equations gives
N f_N = f_{N1} + (N  1) f_{N1} or f_N = f_{N1}
i.e. the probability doesn't depend on the number of passengers.
Obviously in the base case, f_2 = 1/2
so f_N = 1/2

Geeky McGeekface
United States Manassas Virginia
It's time for baseball, people! Pitchers and catchers report soon and the national pastime is with us again!

Spoiler (click to reveal) Yes, it's 50%, regardless of how many passengers and seats there are. Basically, it's as simple as this: will your seat or the dickwad's (first passenger's) seat be occupied first? If at any point, the dickwad's seat is occupied before yours is, you win, since all the boarded passengers seats are occupied (not necessarily by the people who should be in them, but that doesn't matter) and every subsequent passenger will take their proper seat, allowing you to sit in yours. If, OTOH, your seat is occupied before the dickwad's, then you lose. Since whenever there's the chance for one of these two seats to be occupied, the choice is random, there's a 50% chance that the dickwad's seat will be occupied before yours is and that's the probability that your seat will be unoccupied when you board.

Matt
United States Central Coast California
0110100110010110

park0523 wrote: My take: Spoiler (click to reveal) [induction...]
so f_N = 1/2
Nice!
Spoiler (click to reveal) Another way to look at it is the following:
The set of displaced people has to form a single loop (or "cycle") that ends in person #1's seat. If you are displaced, you have to close the loop, and you lose. If somebody before you closes the loop (by sitting in #1's seat), there will be no more displaced passengers after that person in line, so you win.
Look at the last displaced person before you in line. (There has to be such a person.) They either displace you, or they sit in person #1's seat, closing the loop. It doesn't matter where this person is in line, they have an equal chance of picking either of those two seats (since we ruled out the possibility of them picking any other seat). So P=1/2.
Edit: Ninja'ed by Larry while I was typing!

Geeky McGeekface
United States Manassas Virginia
It's time for baseball, people! Pitchers and catchers report soon and the national pastime is with us again!

Verdigris97 wrote: Ninja'ed by Larry while I was typing! I think your proof is a little more rigorous than mine, Matt, but the following version might be better yet:
Spoiler (click to reveal) As you say, look at the last displaced person prior to you to board. If none of Passengers 299 are displaced, then we'll consider Passenger 1 to be that person. Let's call this last displaced person Passenger X. X must have sat in either Passenger 1's seat or in your seat. To prove this, let's say, instead, that X sat in Passenger Y's seat, where Y isn't Passenger 1 or you. Y couldn't have boarded before X, since when he boarded, either he sat in his proper seat or his seat was occupied, forcing him to sit somewhere else. Either way, Y's seat was occupied before X boarded. And if Y boards after X does, he finds X sitting in his seat and he becomes displaced. But we said that X was the last displaced person, so that's impossible as well. So X either sits in Passenger's 1 seat or in your seat, a 50/50 probability. Thus, the probability that your seat is occupied is 50%, regardless of how many passengers there are.

Mark Davidson
United Kingdom Armagh

Spoiler (click to reveal) One other interesting feature of the solution is that if you DO end up in the wrong seat, it'll always be the jerk's seat. Therefore you should put in a complaint to the airline company afterwards, and they can reprimand the passenger appropriately.

Erik Henry
United States Houston Texas

EXTRA CREDIT:
[Warning: Much more difficult]
What if the second person also sat down in a random seat. And the third. And the fourth. And everyone else before you, and then you took the remaining seat. What is the probability that no one is in their correct seat?



Erik17 wrote: EXTRA CREDIT:
[Warning: Much more difficult]
What if the second person also sat down in a random seat. And the third. And the fourth. And everyone else before you, and then you took the remaining seat. What is the probability that no one is in their correct seat?
Spoiler (click to reveal) 1/e! Or more accurately, round(100!/e)/100!

Erik Henry
United States Houston Texas

imHereForTheRiddler wrote: Erik17 wrote: EXTRA CREDIT:
[Warning: Much more difficult]
What if the second person also sat down in a random seat. And the third. And the fourth. And everyone else before you, and then you took the remaining seat. What is the probability that no one is in their correct seat? Spoiler (click to reveal) 1/e! Or more accurately, round(100!/e)/100!
Spoiler (click to reveal) I assume you're just excited by the answer and not actually saying it's 1/e!
This thread has some discussion of the problem:
Interesting probability problem: Ticket holders seated randomly
So it's P = 1  (1/1!) + (1/2!)  (1/3!) + (1/4!) . . . . + (1/100!) which is approx. 1/e
It's amazing how quickly that converges:
Passengers Probability 1 0 2 0.5 3 0.33333 4 0.375 5 0.3666667 6 0.3680556 7 0.3678571 8 0.3678819 9 0.3678792 10 0.3678795
100 0.3678794


