I found this on quora.com.
I’m not sure how to even approach this. I suppose you could just run a large number of simulations, but it seems like there must be a mathematical approach.
First of all, this sounds quite familiar, so it must be a classic exercise rather than original to Quora.com.
Next, there is no need to run simulations; it is possible to work out exactly. Have you tried solving it with a smaller number of people, or drawing a diagram? A hint is that the number of people involved does not really matter.
If it’s only me and the crazy person, then I have a 50% chance of sitting in my assigned seat.
If there’s 3 people then there are three possible ways for the first two to sit. They could sit in 1 & 2, 2 & 3, or 1 & 3. That means that there’s I have a 1 in 3 chance of my sitting in any given seat, including my assigned seat.
So with 100 people, I have a 1 in 100 chance of getting my assigned seat. The situation is analogous to everyone before me sitting in a random seat, since my odds aren’t dependent on who sits in a given seat, just whether or not any of them sit in mine.
Remember, though: passengers (with the one exception) do not choose random seats. They sit in their assigned seats unless one is not available.
Your insight that your odds only depend on whether or not someone takes your seat, and not the details of the arrangement, is key.
Are you saying that my conclusion is wrong?
I think it needs modification. If random guy is 99th in line, I have 50% chance. If he is 98th in line, I have 33% chance, etc…
Yeah. If the crazy person is first in line they have a 1/100 chance of randomly picking their own seat. So your odds must be higher than that since you can also “win” by never having anyone randomly pick your seat.
I don’t think you can say this.
If the crazy guy is 2 spots ahead of you, go through the possibilities one by one:
1/3 he sits in his own seat.
1/3 he sits in your seat.
1/3 he sits in the next guy’s seat, and that guy makes a random choice.
That is:
1/3 he sits in his own seat.
1/3 he sits in your seat.
1/6 he sits in the next guy’s seat, and that guy sits in the crazy guy’s seat.
1/6 he sits in the next guy’s seat, and that guy sits in your seat.
Here is a previous thread about this. The link to the puzzler is broken now, but it is the same problem.
I’m passenger 100. If the crazy passenger is 99, there will be 2 empty seats when he gets on the plane. There’s a 1-in-2 change that he’ll take mine.
If the crazy passenger is 98, there will be 3 empty seats. 1/3 chance he takes his assigned seat. 1/3 chance he takes mine. If he takes the other seat, then that passenger has to choose at random from the two remaining; 1/2 that he takes mine, 1/2 that he takes Mr. Crazy’s. The chance I get my assigned seat is 1-in-2.
I’m gonna take a bit of a guess here that the rest of the cases follow a similar pattern. If Mr. C takes his own seat, then I get my seat. If he takes mine, I’m out of luck. If he takes any other, then the passenger whose seat he takes becomes a new Mr. Crazy, and so on, until someone either sits in my seat (in which case I don’t get it), or the seat given to the original Mr. Crazy (in which case I will get my assigned seat).
So the chance I get my seat is 50%.
I’m fairly sure it’s 50/50.
At some point during the boarding process the crazy guy comes in and sits somewhere. There’s some likelihood he sits randomly in his own seat and some likelihood he sits randomly in my seat. But those two are equally likely. So as long as we end up 50/50 from the case where he sits in a third party’s seat, we will still end up 50/50.
So he sits in a random person’s seat. Then at some point that guy boards, sees that his seat is taken, and sits in some random person’s seat. This chain of displacement continues until one of two things happen, either:
(1) Someone randomly sits in my seat. At that point I “lose”
or
(2) Someone randomly sits in the seat originally assigned to the crazy person. At that point I “win”, because there will be no further conflicts.
But every time someone is making a decision, those two chances are equally likely. So it’s just a matter of which happens first. So it’s 50/50.
So in order to win you have:
[Odds CP picks his own seat] + [Odds everyone randomly does not pick your seat]
Let’s make it easy for now and assume CP is first in line:
The first term is easy, that’s 1/100
Second term is harder. Let’s see the odds for passenger 2 sitting in your seat. Those would be:
[Odds CP picked the second person’s seat] * [Odds second person picks yours]
(1 / 99) * (1/98)
Person 3 would be:
[Odds CP picked the second person’s seat] * [Odds second person picked 3rd person] * [Odds 3rd person picked your seat]
(1/99) * (1/98) * (1/97)
Clearly there is a pattern emerging here. If we sum up all of these odds then we will get our answer. I’m working on a formula for that.
Alice and Bob buy tickets for Seats 1 and 2. Alice gets on first and chooses one of the two seats at random. Either Alice takes her seat and Bob gets his correct seat or Bob must take Alice’s seat. Bob always gets his seat if Alice’s seat is taken.
Alice, Bob and Cheryl buy tickets for Seats 1, 2 and 3. Alice gets on first and chooses one of the three seats at random. If she chooses her seat, everything is fine and Bob and Cheryl board as normal. If she chooses Bob’s seat, he must now choose Alice’s seat or Cheryl’s seat. If he chooses Alice’s seat, Cheryl and Diana can be seated per their tickets. If he chooses Cheryl’s seat, Cheryl must take Alice’s seat. If Alice takes Cheryl’s seat, Bob can sit in his seat and Cheryl must sit in Alice’s seat. Cheryl always gets her seat if Alice’s seat is taken.
Alice, Bob, Cheryl and Diana buy tickets for Seats 1, 2, 3 and 4. Alice boards first and choose one of the 4 seats at random. Bob goes next. If Alice is in Seat 1, everything is fine and everyone is seated correctly. If Alice chooses 2, Bob must sit in Alice, Cheryl or Diana’s seat. If he sits in Alice’s seat, Cheryl and Diana get their own seats. If he displaces Cheryl, when Cheryl gets on, she can take Alice’s empty seat or Diana’s empty seat. If she takes Alice’s seat then Diana gets her seat. If she takes Diana’s, then everyone is in the wrong seat. If Bob chooses Diana’s seat, Cheryl sits in her seat and Diana is forced into Alice’s seat. If Alice takes Cheryl’s seat, Bob alway sits in his correct seat. Cheryl must sit in Alice’s seat, leaving Diana’s free for Diana, or Diana’s seat and forcing everyone into the wrong seat. If Alice takes Diana’s seat, Bob sits in his seat, Cheryl sits in hers and Diana is forced to sit in Alice’s seat. Diana always gets her seat if Alice’s seat is taken.
I think that when the last person in the line boards the plane, either their seat or Alice’s seat is free, regardless of the number of people who board the plane and making the odds of getting the correct seat 50%.
Right. At some point before you board the plane, someone is going to pick your seat or the crazy guy’s seat. When they make that choice, both seats are equally likely. Nothing else affects the probability, so it’s 50-50.
I agree:
Let’s do all the possibilities for a 4 person seat.
CP sits in his own seat - Win (1/4)
CP sits in your seat - Lose (1/4)
CP sits in person 2’s seat (1/4)
—Person 2 sits in your seat - Lose (1/3)
—Person 2 sits in his seat - Win (1/3)
—Person 2 sits in person 3’s seat ( 1/3)
------Person 3 sits in his seat Win (1/2)
------Person 3 sits in your seat Lose (1/2)
CP sits in person 3’s seat (1/4)
—Person 2 sits in his own seat (1/1)
------Person 3 sits in your seat - Lose (1/2)
------Person 3 sits in his seat - Win (1/2)
Wins are:
1/4 + (1/4)(1/3) + (1/4)(1/3)*(1/2) + (1/4) * (1/1) * (1/2) = 1/2
“crazy guy” is so non-PC. Let’s stick to clinical terms like “mentalist”, “binner”, and “circus freak”.
There’s another case to consider. CP may have taken P2’s seat, and P2 took P3’s, and P3 took mine (which is what you describe); or CP took P3’s seat (1/99), P2 took his own seat (1/1, by the definition of the problem), and P3 took mine (1/97).
If you can work this out all the way to its conclusion, more power to you. But it’s gonna get really hairy, really fast. I’ll stick with my and Max’s answer for now.
Pronoun trouble. I’d rephrase those bolded lines to “Person X sits in CP’s seat”.
I think the version in that thread presumes that the “crazy person” is the first passenger to board. But it turns out that that doesn’t affect the solution.
Proof by induction on n, the number of passengers who get on before you, that the answer is 50%:
If n = 1, that one passenger before you is the crazy person, and there’s a 50-50 chance he chooses your seat.
Now assume it’s true for n = k, and consider what happens when n = k+1.
If the first passenger to board is not the crazy passenger, there are k remaining passengers ahead of you, so by the inductive hypothesis there’s a 50% chance you’ll get your own seat.
If the first passenger to board is the crazy passenger, then the argument Xema gave in the other thread applies:
You can look at it as an induction problem like that if you want to; that’s the way I did it at first (and in the old thread, which I see I posted in :)). But it really isn’t necessary to worry about all that.