Mark Davidson
United Kingdom
Armagh
flag msg tools
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/will-someone-be-sitting-...
1 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
¡dn ʇǝƃ ʇ,uɐɔ ı puɐ uǝllɐɟ ǝʌ,ı
Canada
Chestermere
Alberta
flag msg tools
Life lesson: Hamsters are NOT diswasher safe.
badge
There are 10 types of people-- those who understand binary, and those who don't.
Avatar
mbmbmbmbmb
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?
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Mark Davidson
United Kingdom
Armagh
flag msg tools
I think the solution is:

Spoiler (click to reveal)
50%


I'll hold out on posting my workings until later.
2 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Doctor Tom
England
flag msg tools
badge
Avatar
mbmbmbmbmb
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
1 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Mark Davidson
United Kingdom
Armagh
flag msg tools
Spoiler (click to reveal)
Hint: Think about the scenario that someone picks the first passenger's seat at random
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Doctor Tom
England
flag msg tools
badge
Avatar
mbmbmbmbmb
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 1-99, plus the same again [from working backwards?]
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Matt Parker
msg tools
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_{N-1} )

or

N f_N = 1 + f_2 + f_3 + f_4 + ... + f_{N-2} + f_{N-1}

Now look at the case for a plane with N-1 passengers

(N - 1) f_{N-1} = 1 + f_2 + f_3 + ... + f_{N-2}

Combining these two equations gives

N f_N = f_{N-1} + (N - 1) f_{N-1}
or
f_N = f_{N-1}

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





3 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Geeky McGeekface
United States
Manassas
Virginia
flag msg tools
designer
badge
It's time for baseball, people! Pitchers and catchers report soon and the national pastime is with us again!
Avatar
mbmbmbmbmb
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.
5 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Matt
United States
Central Coast
California
flag msg tools
0110100110010110
badge
Avatar
mbmbmbmbmb
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!
2 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Geeky McGeekface
United States
Manassas
Virginia
flag msg tools
designer
badge
It's time for baseball, people! Pitchers and catchers report soon and the national pastime is with us again!
Avatar
mbmbmbmbmb
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 2-99 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.
2 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Mark Davidson
United Kingdom
Armagh
flag msg tools
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.
4 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Erik Henry
United States
Houston
Texas
flag msg tools
badge
Avatar
mbmbmb
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?
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Mike Donner
msg tools
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!
1 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Erik Henry
United States
Houston
Texas
flag msg tools
badge
Avatar
mbmbmb
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! laugh

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

1 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Front Page | Welcome | Contact | Privacy Policy | Terms of Service | Advertise | Support BGG | Feeds RSS
Geekdo, BoardGameGeek, the Geekdo logo, and the BoardGameGeek logo are trademarks of BoardGameGeek, LLC.