# Interesting math puzzle. **URL:** \ **Category:** Miscellaneous and Personal Stuff I Must Share\ **Created:** [September 14, 2017, 3:48pm UTC](https://boards.straightdope.com/t/interesting-math-puzzle/796322 "2017-09-14T15:48:29Z")\ **Posts on this page:** 20\ **Page:** 1
**Author:** ![davidm](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/davidm/32/225_2.png) [@davidm](https://boards.straightdope.com/u/davidm)\ **Post date:** [September 14, 2017, 3:48pm UTC](https://boards.straightdope.com/t/interesting-math-puzzle/796322/1 "2017-09-14T15:48:29Z")
I found this on [quora.com](http://quora.com). > **[What is your favorite math problem/puzzle?](https://www.quora.com/What-is-your-favorite-math-problem-puzzle/answer/John-Coiner?srid=39D4L)** > > Answer (1 of 79): A Challenge: > > Before leaping straight to the answer and my elaboration with example, Try your presence of mind and mathematical ability to solve. Yes! Try to check your excellence. So, here we go, > > (Stop scrolling here and think... > [@](#): > > There are 100 people waiting in line to board an airliner with 100 seats. > > The seats are numbered from 1 to 100. Each passenger holds a ticket with his seat number. > > You are the last passenger in line. > > One of the passengers ahead of you in line is crazy. We don’t know which one. He will ignore his seat assignment and sit in a random empty seat. > > Every other passenger will sit in their assigned seat — unless it is already taken, in which case they too will sit in a random empty seat. > > Passengers board one by one. > > What is the probability that you will sit in your assigned seat? > > EDIT for clarification: the crazy person might sit in his assigned seat; he is equally likely to sit in any open seat. 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. ---
**Author:** ![DPRK](https://avatars.discourse-cdn.com/v4/letter/d/4491bb/32.png) [@DPRK](https://boards.straightdope.com/u/DPRK)\ **Post date:** [September 14, 2017, 4:03pm UTC](https://boards.straightdope.com/t/interesting-math-puzzle/796322/2 "2017-09-14T16:03:01Z")
First of all, this sounds quite familiar, so it must be a classic exercise rather than original to [Quora.com](http://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. ---
**Author:** ![davidm](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/davidm/32/225_2.png) [@davidm](https://boards.straightdope.com/u/davidm)\ **Post date:** [September 14, 2017, 4:25pm UTC](https://boards.straightdope.com/t/interesting-math-puzzle/796322/3 "2017-09-14T16:25:50Z")
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. ---
**Author:** ![DPRK](https://avatars.discourse-cdn.com/v4/letter/d/4491bb/32.png) [@DPRK](https://boards.straightdope.com/u/DPRK)\ **Post date:** [September 14, 2017, 4:32pm UTC](https://boards.straightdope.com/t/interesting-math-puzzle/796322/4 "2017-09-14T16:32:42Z")
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. ---
**Author:** ![davidm](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/davidm/32/225_2.png) [@davidm](https://boards.straightdope.com/u/davidm)\ **Post date:** [September 14, 2017, 5:15pm UTC](https://boards.straightdope.com/t/interesting-math-puzzle/796322/5 "2017-09-14T17:15:41Z")
Are you saying that my conclusion is wrong? ---
**Author:** ![Grrr](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/grrr/32/146_2.png) [@Grrr](https://boards.straightdope.com/u/Grrr)\ **Post date:** [September 14, 2017, 5:24pm UTC](https://boards.straightdope.com/t/interesting-math-puzzle/796322/6 "2017-09-14T17:24:02Z")
> [@davidm](#): > > 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… ---
**Author:** ![treis](https://avatars.discourse-cdn.com/v4/letter/t/bc79bd/32.png) [@treis](https://boards.straightdope.com/u/treis)\ **Post date:** [September 14, 2017, 5:30pm UTC](https://boards.straightdope.com/t/interesting-math-puzzle/796322/7 "2017-09-14T17:30:34Z")
> [@davidm](#): > > Are you saying that my conclusion is wrong? 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. ---
**Author:** ![borschevsky](https://avatars.discourse-cdn.com/v4/letter/b/97f17d/32.png) [@borschevsky](https://boards.straightdope.com/u/borschevsky)\ **Post date:** [September 14, 2017, 5:31pm UTC](https://boards.straightdope.com/t/interesting-math-puzzle/796322/8 "2017-09-14T17:31:43Z")
> [@davidm](#): > > That means that there’s I have a 1 in 3 chance of my sitting in any given seat, including my assigned 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. ---
**Author:** ![MentalGuy](https://avatars.discourse-cdn.com/v4/letter/m/439d5e/32.png) [@MentalGuy](https://boards.straightdope.com/u/MentalGuy)\ **Post date:** [September 14, 2017, 5:35pm UTC](https://boards.straightdope.com/t/interesting-math-puzzle/796322/9 "2017-09-14T17:35:19Z")
Here is a p[revious thread about this](http://boards.straightdope.com/sdmb/showthread.php?t=279195). The link to the puzzler is broken now, but it is the same problem. ---
**Author:** ![Robot\_Arm](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/robot_arm/32/18280_2.png) [@Robot\_Arm](https://boards.straightdope.com/u/Robot_Arm)\ **Post date:** [September 14, 2017, 5:40pm UTC](https://boards.straightdope.com/t/interesting-math-puzzle/796322/10 "2017-09-14T17:40:34Z")
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%. ---
**Author:** ![MaxTheVool](https://avatars.discourse-cdn.com/v4/letter/m/9fc29f/32.png) [@MaxTheVool](https://boards.straightdope.com/u/MaxTheVool)\ **Post date:** [September 14, 2017, 5:55pm UTC](https://boards.straightdope.com/t/interesting-math-puzzle/796322/11 "2017-09-14T17:55:05Z")
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. ---
**Author:** ![treis](https://avatars.discourse-cdn.com/v4/letter/t/bc79bd/32.png) [@treis](https://boards.straightdope.com/u/treis)\ **Post date:** [September 14, 2017, 5:56pm UTC](https://boards.straightdope.com/t/interesting-math-puzzle/796322/12 "2017-09-14T17:56:44Z")
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. ---
**Author:** ![Inner\_Stickler](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/inner_stickler/32/318_2.png) [@Inner\_Stickler](https://boards.straightdope.com/u/Inner_Stickler)\ **Post date:** [September 14, 2017, 6:01pm UTC](https://boards.straightdope.com/t/interesting-math-puzzle/796322/13 "2017-09-14T18:01:03Z")
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%. ---
**Author:** ![borschevsky](https://avatars.discourse-cdn.com/v4/letter/b/97f17d/32.png) [@borschevsky](https://boards.straightdope.com/u/borschevsky)\ **Post date:** [September 14, 2017, 6:04pm UTC](https://boards.straightdope.com/t/interesting-math-puzzle/796322/14 "2017-09-14T18:04:59Z")
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. ---
**Author:** ![treis](https://avatars.discourse-cdn.com/v4/letter/t/bc79bd/32.png) [@treis](https://boards.straightdope.com/u/treis)\ **Post date:** [September 14, 2017, 6:07pm UTC](https://boards.straightdope.com/t/interesting-math-puzzle/796322/15 "2017-09-14T18:07:51Z")
> [@MaxTheVool](#): > > 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. 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 ---
**Author:** ![DPRK](https://avatars.discourse-cdn.com/v4/letter/d/4491bb/32.png) [@DPRK](https://boards.straightdope.com/u/DPRK)\ **Post date:** [September 14, 2017, 6:11pm UTC](https://boards.straightdope.com/t/interesting-math-puzzle/796322/16 "2017-09-14T18:11:54Z")
“crazy guy” is so non-PC. Let’s stick to clinical terms like “mentalist”, “binner”, and “circus freak”. ---
**Author:** ![Robot\_Arm](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/robot_arm/32/18280_2.png) [@Robot\_Arm](https://boards.straightdope.com/u/Robot_Arm)\ **Post date:** [September 14, 2017, 6:15pm UTC](https://boards.straightdope.com/t/interesting-math-puzzle/796322/17 "2017-09-14T18:15:51Z")
> [@treis](#): > > 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. 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. ---
**Author:** ![Robot\_Arm](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/robot_arm/32/18280_2.png) [@Robot\_Arm](https://boards.straightdope.com/u/Robot_Arm)\ **Post date:** [September 14, 2017, 6:21pm UTC](https://boards.straightdope.com/t/interesting-math-puzzle/796322/18 "2017-09-14T18:21:42Z")
> [@treis](#): > > 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) Pronoun trouble. I’d rephrase those bolded lines to “Person X sits in CP’s seat”. ---
**Author:** ![Thudlow\_Boink](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/thudlow_boink/32/320_2.png) [@Thudlow\_Boink](https://boards.straightdope.com/u/Thudlow_Boink)\ **Post date:** [September 14, 2017, 6:23pm UTC](https://boards.straightdope.com/t/interesting-math-puzzle/796322/19 "2017-09-14T18:23:11Z")
> [@MentalGuy](#): > > Here is a p[revious thread about this](http://boards.straightdope.com/sdmb/showthread.php?t=279195). The link to the puzzler is broken now, but it is the same problem. 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: > [@This weeks Car Talk Puzzler (Probability)](https://boards.straightdope.com/t/this-weeks-car-talk-puzzler-probability/267569/27): > > How about an argument for 50%, based on symmetry: > > There are two special seats: yours (call it Y), and the one that was assigned to the first passenger to board (call it F). If any passenger after the first happens to sit in F before Y is occupied, you will get to sit in Y. But if anyone grabs Y before F is occupied, you will not get to sit in Y. As there is nothing to make either of these more likely than the other, the chances are equal. > > Does that work? ---
**Author:** ![borschevsky](https://avatars.discourse-cdn.com/v4/letter/b/97f17d/32.png) [@borschevsky](https://boards.straightdope.com/u/borschevsky)\ **Post date:** [September 14, 2017, 6:26pm UTC](https://boards.straightdope.com/t/interesting-math-puzzle/796322/20 "2017-09-14T18:26:44Z")
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. [Next page](https://boards.straightdope.com/t/interesting-math-puzzle/796322.md?page=2)