That was my first thought too, it'd be so funny that a person could just answer that at an interview and be right this time. A broken clock is right twice a day! LOL.
In "Always Sunny...", according to Mac, Charlie has a 50% of having sex with the woman in the back room of Guigino's Restaurant prepared by Dennis while their milk steaks are being cooked because she either says yes or no.
Here are the details for anyone interested. We do it by induction Notation: Let p_n be the probability that you sit in your seat when there are n people P(event) is the probability of that event happening Base case: n=2, this is proved in video to be p_2 = 1/2 Induction: We come up with a formula for p_n in terms of the previous probabilities for n>2. For the motivation behind this, it is the 3 cases he went over in the video p_n = P(1 sits in seat 1) (this is case 1) + P(1 sits in seat 2)*p_(n-1) + P(1 sits in seat 3)*p_(n-2) + ... + P(1 sits in seat n-1)*p_2 (this is case 3) + P(1 sits in seat n)*0 (this is case 2) This comes from the law of total probability, and we can see that if 1 sits in seat k, then everyone is going to sit in their own seat until person k, and at that time we have the same problem but with k of the n seats taken up, therefore the k'th person becomes the new person 1, and we have n-k+1 empty seats on the plane. We also note that if 1 sits in seat n in case 3, they have sat in your seat as you are person n, so the probability of you sitting in your seat is 0. Writing this with a sum gives p_n = 1/n + sum from k=2 to n-1 of 1/n * p_k = 1/n * (1 + sum from k=2 to n-1 of p_k). Now we use the induction hypothesis where we assume that for k
@Henry Ginn According to this p_3 = 1/3 (case1)+ (1/3)*0 (case2)+ (1/3)*0(case3) = 1/3. Also by the definition of p_n isnt p_1 = 1, because you are only person and you get your seat. so there is a little mistake in this proof or am I mistaken? great proof btw
@JZ's Best Friend very lucky I would say, because you would appear smart when you guess all the answers in an exam anyway lol, plus then you could get a lottery ticket and win
Notice that this is equivalent: Passenger number 1 picks a random seat. When the owner of the seat comes, passenger 1 stands up and picks another random seat. Why is this equivalent? Because it doesn't matter to us who ends up at our seat, only if there is someone there in the end. It's obvious that passenger 1 ends up at our seat if they pick it before they get the chance to pick theirs. These two events are equally probable at each step, so there is a 50% chance that passenger 1 ends up at our seat.
@@paulfoss5385 thanks bro. Not so related, but this is what I love about math/programming olympiad problems. There is almost always a perspective that makes the problem easy
Nice! There are bassicly two 'sinks'; one at the seat of passenger 1, and one at our seat. There is nothing that makes one be more attractive than the other, so at the end, when we board the plane, there is a 50/50 which one where the flow stopped.
I too got this at a Microsoft interview back when they asked questions like this. The “trick” to this type of brain teaser is always to start with the smallest case you can and use induction. Once you know that, these become silly.
It's not just for induction type problems. You can often gain insight on a lot of math problems by doing smaller and less complex versions of the problem, and it's usually the first thing you do if possible.
@@PentaCorpStudio find the next number in the sequence: 1,2,3,4,5, ? Looks can be deceiving, n+[(n-1)(n-2)(n-3)(n-4)(n-5)]. Turn out it's 120 (Correction: 126)
@@PentaCorpStudio I understand. I knew it wasn't meant for you but as a companion comment for the general public. On the topic of things may not be what they seem
Much easier solution: Notice that the last passenger can only sit in his original seat or the first passengers seat, since if he sat on some other intermediate passengers seat, then that intermediate passenger must have skipped his perfectly empty seat which is a contradiction. Now we know that the last passenger can only sit in his seat or 1st seat, we can argue by the symmetry that they are of equal probability: If you don’t provide the first passenger and the last passenger their tickets, everything would just be the same.
@@cletushumphrey9163 Suppose that we give the tickets of the 1st and the last person only to you. Would that effect anything in the game? Surely it doesn't effect the first person, he"s already going to lose it and sit at a random position. It also doesn't affect the last person since the poor fella is going to sit at any seat that will be left to him by 99 people that boarded before. Okay, now only you know the real seats. So for anybody that boards the plane (all 100 of them), the seat belonging to ticket A (originally 1st persons) and the seat belonging to ticket B (100th persons) are equivalent. They have no clue which belongs to which. With this equivalency, we wouldn't expect the last person to sit in one particular seat than the other if we do this experiment over and over again.
@@musicalchicken1024 it's more formal than his. He needs to show the pattern explicitly and compute it for arbitrary number of passengers n. Besides, you don't need numbers for formal proof. The ideas matter at the end. Simpler is better.
Another perspective: since we only care whether our own seat is filled by SOMEBODY, we can re-frame the problem (perhaps more plausibly) as follows: passenger 1 sits in a random seat. If that's someone else's assigned seat, that passenger will kick P1 out of the seat, and then P1 will pick another random seat to sit in, and then perhaps get kicked out of that one, and so on. This is effectively equivalent to the problem as given, since in any case we have one person remaining in the assigned seat, and one person picking an empty seat at random to fill. When we look at it this way though, it immediately reveals the "cycle" structure: the only seat passenger 1 will not be eventually kicked out of is his own seat or your seat, and each is equally likely. This perspective also lets us quickly solve a more general problem: if you're passenger number M when there's N total passengers, and the seating is done randomly in this way, what is the probability that you get to sit in your assigned seat? Well, if we take the perspective of passenger 1 repeatedly getting "kicked out," when it's your turn to sit, we see that passengers 2 through M-1 must be in their seats (in the original framing, that means seats 2 thru M-1 are filled), and then one seat outside of those is filled at random by passenger 1. The probability that it is seat M, i.e. your seat, that is filled when it's your turn to sit is 1/(N-(M-2)), since P1 is sitting in one of the N-(M-2) remaining seats at random. If we plug in M = N then we get back the original result, as expected.
Love the logic and the video, but at first I was like, "100% I'll have my seat, since the passenger that lost his ticket won't be allowed on the plane!!" lol
Change the problem so that Passenger 1 finds a random seat, but when the right owner gets there, Passenger 1 moves to another random spot. Note this is the same problem, since we don't care WHO is moving around, just whether our seat is open or not. This continues until Passenger 1 either gets their own seat, after which we get our own, or Passenger 1 gets our seat, after which we don't. The probability he selects Seat 1 or Seat 100 is equally likely, no matter how many spots are left. So after this process, the probability must be 1/2.
I thought about writing the solution adding some of my thought process to justify some steps, so to anyone who may interest: In the case with n passengers, there's: The chance of the first passenger choosing their own seat (you get your seat) P = 1/n The chance of them choosing the last passenger seat (you don't get your seat) P = 1/n The chance of them choosing one of the other seats P = (n-2)/n Now we just have to find what is the chance of you getting your seat in the last case (in the first case it's 1 and in the second one it's 0). We can intuitively see it's 1/2, since the seats are identical and in the end it's the first seat that is free or your seat that is free, so it would make sense for the probabilities of these cases to be the same. We can prove it rather simply, by noting that, for each case in wich one person occupies the first seat, there's an equally likely case in wich that person occupies the last seat, maintaining the same configuration for the other passengers. And therefore we've proven, I hope more rigorously, that the chance of you getting your seat in the last case is 1/2. So we have the final probability of (1/n)*1 + (1/n)*0 + ((n-2)/n)*(1/2) = 1/2
One really nice observation: any passenger n has a probability of (101 - n) / (102 - n) to find their assigned seat. So, for example, passenger 2 has a 99/100 chance of finding his assigned seat, passenger 3 has a 98/99 chance, and so on, all the way down to the hundredth passenger having a 1/2 chance. Note: formula does not apply to passenger 1 (the passenger who lost his ticket)
Here’s a more rigorous inductive solution. Replace 100 with n and induct on n. Let p_k denote the probability that the last person gets their seat, we claim p_n = 1/2 for all positive integers n. For our base case, p_2 = 1/2 is clearly true. Now, assume our result holds for all ms. Thus, the seats 1,2,...,s can be ignored and we have a situation equivalent to the m-s person case which we know has probability 1/2. Notice that the probability of any given s is chosen is uniform and thus the total probability is 1/2. Completing the induction.
So if the first person chooses corrently, everyone goes to their correct seats. But if not, then chaos. Kinda like the double pendulum, the initial starting conditions matter the most
And away from the platonic realm what will actually happen is a fight will break out; security will be called; the delay will cause the flight crew to run out of hours and everybody will be deplaned to wait for a backup crew.
Nice, this one is really logical. We're just waiting for the misplaced passenger to pick the seat of the 1st passenger or your seat. If any of the others are taken, we wait a set of iterations before we get a new misplaced passenger, and this process repeats until either your seat is taken or the seat of the 1st passenger is taken. At the end of the day, the only probability we're measuring in a meaningful way is between the 50/50 between your seat and the 1st guy's seat. If any of the other seats get taken, we just delay the process until we eventually see the result of the 50/50.
Perhaps the simplest way to think about it is the following. The last person to board has only 1 seat available. That seat is either the person's seat or someone else's seat. So there's a 1/2 chance it's the person's seat. To be more precise, the last seat must be either the last person's seat (person n's seat) or person 1's seat, because when everyone else sat down, either someone took person 1's seat, or did not.
Nice problem. The confusing part is that this constant 50% probability applies only for the very last passenger. For example, second passenger's (out of the 100) chance to get their seat is 99%
We can use the "symmetry" argument to get the probability for everyone. If there are N seats on the plane and the first person does not have a ticket and sits anywhere, then the last person to board gets their seat with probability 1/2. The second last person gets their seat with probability 2/3. The third last with 3/4 etc. In general, for the Kth last person to board (K = 1 to N-1), the probability they get their seat is K/(K + 1). To see this, we identify the seats of the last K people to board, plus the seat of the first to board. That's a set of K + 1 seats. The Kth last to board gets their seat as long as one of the other K seats get occupied before theirs. These seats are occupied with equal probability by any of the first N-K passengers who are looking for a spare seat because theirs is occupied. That gives a probability of 1/(K+1) that their seat is occupied by the time they board. Or, K/(K+1) that it is not occupied and they get their seat.
Here’s the thing, if someone lost their ticket they wouldn’t even be let through the departure gate… so theoretically, there’d be a spare seat… Who the heck loses their boarding pass that quickly??
We can prove this by induction very simply. Prove base case 1/2. Then assume it holds for at least n-1 passengers. Then for n passengers either the first dude picks their own seat (prob 1/n) or picks one of the other seats except for the last seat (prob = (n-2)/n ). Now we can imagine that the seat of the person that the first dude takes is reassigned to them. In this way, we can use the inductive hypothesis to see that this has prob 1/2 of working out. So in total 1/n + [ (n-2)/n ] (1/2) = 1/2 as desired.
A really simple approach: imagine that we have a 6-sided die, and we perform the following experiment: if the result of the first throw is 1 or 6, we stop. Otherwise, we throw the die again until we hit 1 or 6. The only outcomes that have a positive probability are 1 and 6, and since both are equally likely, p(1) = p(6) = 1/2. This is exactly what is happening here: let A be the event where the n-th passenger sits in his seat. The first passenger chooses a number between 1 and n uniformly. If the result is 1, then A holds; if it's n, A can't happen; and if he chooses a seat i, 1 < i < n, then we ignore the result of the experiment and repeat it with passenger number i. Now he repeats the experiment with the available seats: if the result is 1 or n, we can conclude the same as before; otherwise, we just ignore the outcome and repeat this process again. This process can be thought of as throwing an n-sided fair die: if the result is different from 1 and n, we just repeat the experiment with a smaller die (with size equal to the number of available seats) until we obtain 1 or n. Since the sizes are decreasing, this process ends in a finite number of steps. In this probability space, the support of p is just {1, n}, and since both events are equally likely, p(A) = p(A^c) = 1/2.
I elaborated the following solution, I like it because it is both rigorous and short: let's define P(s) the probability of ending up on your seat "plane problem" for s seats, Now notice that - if passenger1 seats on the last but one seat, then the probability of ending in your correct seat is P(2) - if passenger1 seats on the last but two seat, then the probability of ending in your correct seat is P(3) - if passenger1 seats on the last but three seat, then the probability of ending in your correct seat is P(4) and so on and so forth So P(s) = 1/s + P(2)/s + P(3)/s + ... + P(s-1)/s (Eq. 1) where the first 1/s is the probability that passenger1 sits on the first seat. Now, following the previous definition we can rewrite Eq. 1 as: P(s-1) = 1/(s-1) + P(2)/(s-1) + ... + P(s-2)/(s-1) (Eq. 2) But then we can group all `s-1` terms of Eq. 1 as terms of P(s-1) as shown in Eq. 2, and we can write P(s) = (s-1)/s P(s-1) + P(s-1)/s Which is identical to P(s) = P(s-1) And, thus P(s) = P(2) And we know that P(2) = 1/2 And that proves it!
Wouldn't a 50% chance assume you have the probability of sitting in any seat? Wouldn't it just be a 1/100 or 1% chance given if the seat you choose is assumed at 50% and you can't sit there the next seat wouldn't be 50% chance it would just lower based on probability?
It is a really cool video. But I would have have liked to see an induction prove of this answer. Again, really cool problem and a simple and easy to understand answer
Oh my god i took one look at this and said “these trick questions always on some bullshit its gotta be like 50/50 or something” with 0 actual evidence im dead
Here's a different (and quite elaborate) solution: Let's use 1, 2, ..., 100 as shorthand for each person, assigning each the number of their original seat.. If you (100) couldn't get your place, then someone else before you must have taken it, and as such someone else must have taken _their_ place, and so on, so you get a chain j_1 -> j_2 -> ... -> j_k where 1 = j_1 > j_2 > ... > j_k = 100 and person j_m takes the place of person j_{m+1}. And _everybody else went to the correct seat._ The probability of this particular chain happening is: 1/100
After the second person sits down, there will be one person in two's assigned seat and one person on a random seat. This goes up until after 99 people sit down, there will be 98 people in assigned seats and 1 person in a random seat. The last person then has a 50% chance to get their assigned seat.
Simpler solution: Before it gets to your turn, either your seat has been chosen or not (by anyone). Since there are equal number of people and seats, your seat has not been chosen if and only if the first person's seat has been chosen. For each person to sit before you, it's equally likely that they will choose the first person's seat vs your seat (if they are forced to sit in their own seat, which is guaranteed to happen if anyone before has chosen either the first person's seat or your seat, then both of these probabilities are zero). Since it's equally likely for each person to choose your seat vs the first person's seat, overall it's equally likely that the first person's seat has been chosen vs your seat has been chosen when it comes to your turn. In other words, you have fifty percent chance of sitting in your own seat, and fifty percent chance of sitting in the first person's seat.
Three people answer 50% 1) Here's my proof, QED. 2) I have some intutuin that its 1/2 but wouldn't know where to begin prooving it. 3) Either you have your seat or you don't.
in the real world the second passenger will tell the first passenger "you got my seat you have to move" and this will keep happening until the first passenger finds his actual seat because the flight attendants will figure out he doesnt have a ticket and make him wait until everyone else is seated.
In Real Life everyone would tell him to take his seat as the last person, because the other 99 know their seats. But then there would be no interesting math question XD
Hmm does this actually check out with preferences. Like with wordle, the odds of finding all valid words isn't the actual probability of commonly use words. So seats specifically up front is more likely to be "randomly choosen" leaving lower chance if your seat was up front and higher in the rear. Does it still map out irl to 50 percent?
If you're the LAST PASSENGER to board, then either yours is the one remaining unoccupied seat or it isn't. How this situation developed isn't very interesting. It's a Markov chain in theory, but the real conditions are messier, because someone displaced from their assigned seat will not choose uniformly from the set of empty seats but will greatly favor the nearby seats, and there will be nonuniform demand for window seats not over the wings, and so on. These effects almost certainly dominate the probability distribution, and yet we don't have usable metrics for them. So, to a good approximation, the probability that the last passenger finds his seat unoccupied is the same as the probability of having any particular seat: 1/100. Close enough, and it took ten seconds to figure out. Now what's for lunch?
The probability is 100%. I'm sitting in my seat whether or not there is a person cushion. If there is a person cushion, then they can hunt around for their seat.
It’s easy for me to say it will be 100 because most people don’t want to walk far from the spot they are currently standing. I got this as a random recommendation and didn’t want to try any math.
Then same happens when you pick a ball in a box where there are initially n red balls and n white balls without putting the ball you picked back in the box, during the k pick, the probability to pick a red ball is always one half
I remember doing something similar a while back. I think you just need to get that no matter what, the last passenger can only sit in 1st or last seat (as any seat between 2 and 99 would have been taken by its own passenger). And then you prove that each passenger has the same probability to sit in 1st or 100th seat at each step, so you end up with P = ½. I'll still watch the video though, can't hurt to learn new stuff (:
for me it was just more intuitive to go backwards, math stays the same. if the 1st person sits in the 100th seat then there's a 100% chance the 100th person will sit in the 100th seat but that'll happen 1/100 times if the 1st person sits in the 100th seat then there's a 0% chance the 100th person will sit the 100th seat but that'll happen 1/100 times _____________________________________________________________________________________________________________________ if the 1st person sits in the 99th seat then everyone till the 99th person will sit in their own seat and when the 99th person's turn to sit comes he'll have the choice of the 1st or the 100th seat, so there's a 50% the 100th seat will remain empty if the 1st person sits in the 98th seat then everyone till the 98th person will sit in their own seat and when the 98th person's turn to sit comes he'll have the choice of the 1st or the 99th or the 100th seat, so 33% chance he sits on the 100th seat and another 33% he sits on the 99th seat (and if he does, there's a 50% chance the 99th person will seat in the 100th seat) so 1/3 + 1/3*1/2 = 50% the 100th seat will remain empty seeing the pattern, it's fair to say it'll stay 50% (I went till the 97th seat just to make sure) as we continue to go backwards as the person sitting on the 1st or the100th seat evens out to 50%.
Only first class gets fucked up. Because seat 1 affects 99.9% of a full plane, because 1 seat is stolen, and the rest would mess up by taking another persons assigned seat.
The problem is simpler than you’re making it, the airline has a record of which seat you’re supposed to be in, so they would make the first passenger sit in their correct seat or not let them board in the first place.
cool, i guessed %50 thinking, either guy get the seat or not, all other info is superfluous and just complicates the real equation. As you said, always comes down to the passage RIGHT BEFORE you having to choose, do I take seat a or b regardless of amount of passengers
Help me out, here. I understand all the various arguments put forward in comments as to why the solution is 1/2. For a laugh, I am trying to work out the case for n=4, but I am getting 1/4+1/12+1/8=11/24. What am I doing wrong? 1/4 probability that 1 sits in my place. 1/12=1/4*1/3 probability that 2 sits in my place. 1/8=1/4*1/2 probability that 3 sits in my place.
Call the passengers P1, P2, P3, and P4, and likewise the seats S1 - S4. The probability that P2 sits in S4, given that P1 didn't take S4, is: (prob P4 in S2)(prob P2 chooses S4) = (1/4)(1/3) = 1/12. So you're right that, after P1 and P2 have sat, the probability of either P1 or P2 is in S4 is 1/4 + 1/12 = 1/3. Obviously, already knowing that the answer is that 1/2 time one of P1, P2 or P3 sits in S4, it must be that the probability that P3 sits in S4 is: 1/2 - 1/3 = 1/6. Thus your claim that there's a 1/8-th chance that P3 ends up in S4 is wrong, but since you didn't give an argument for it, it's not clear what your mistake is. If you want to see how the conditional probabilities work in mindlessly direct & messy detail, it's like this: Let E = "Someone else in S4" = "P4 did not end up in S4". Prob(E) = SUM{ i=1 to 4 of: prob(E|"P1 in Si") prob("P1 in Si") } = (1/4) SUM{ i=1 to 4 of: prob(E|"P1 in Si") } = (1/4) SUM{ i=1 to 3 of: prob(E|"P1 in Si") } + (1/4) prob(E|"P1 in S4") = (1/4) SUM{ i=1 to 3 of: prob(E|"P1 in Si") } + (1/4)(1). Now, for 1
Here's the 4 passenger game by possibilities [and their associated probabilities] - P1 in S1, then order seats filled: S1, S2, S3, S4 [1/4] - P1 in S2, then [1/4] -- P2 in S1, then order seats filled: S2, S1, S3, S4 [(1/4)(1/3)] -- P2 in S3, then [(1/4)(1/3)] --- P3 in S1, then order seats filled: S2, S3, S1, S4 [(1/4)(1/3)(1/2)] --- P3 in S4, then order seats filled: S2, S3, S4, S1 [(1/4)(1/3)(1/2)] -- P2 in S4 order seats filled: S2, S4, S3, S1 [(1/4)(1/3)] - P1 in S3, then P2 in S2, then [1/4] -- P3 in S1, then order seats filled: S3, S2, S1, S4 [(1/4)(1/2)] -- P3 in S4, then order seats filled: S3, S2, S4, S1 [(1/4)(1/2)] - P1 in S4, then order seats filled: S4, S2, S3, S1 [1/4] The the possible sequences of seat-taking with 4 passengers are [w/probability]: S1, S2, S3, S4 [1/4] S2, S1, S3, S4 [1/12] S2, S3, S1, S4 [1/24] S2, S3, S4, S1 [1/24] (E) S2, S4, S3, S1 [1/12] (E) S3, S2, S1, S4 [1/8] S3, S2, S4, S1 [1/8] (E) S4, S2, S3, S1 [1/4] (E) Note: Total = 2(1/4) + 2 (1/8) + 2(1/12) + 2 (1/24) = 6/12 + 3/12 + 2/12 + 1/12 = 12/12 = 1. (whew!) Total producing E (someone else in 4th seat) = 1/24 + 1/12 + 1/8 + 1/4 = 1/24 + 2/24 + 3/24 + 6/24 = 12/24 = 1/2. Also, note that passenger 3 sits in the 4th seat when column 3 has an S4, so the probability of passenger 3 in seat 4 is: 1/24 + 1/8 = 1/24 + 3/24 = 4/24 = 1/6. (You had this probability being 1/8.)
actually it is pretty unlikely you will end up in the first passengers seat, since you are the last person to enter the plane, meaning if the first person takes the seat of the 12th person, which takes the seat of the 33d person, which takes the seat of the 52nd person and so on, each person in the cicle has a probability to choose the first passengers seat, which makes it more unlikely that his seat is being passed out on throughout the entire circle until it is the last seat available to you.
Sorry, but this is against IATA regulations. Also, there is a printed passenger list that the cabin crew would have. In a total failure of all computer systems involved, you would be asked to step aside, let everybody with their boarding passes board, and then sit down at any available seat (which in a case of a fully booked flight would be yours).
I can't imagine the interviewer wanted you to say "well I tested the 2 and 3 cases and they were 50%, so I'm gonna assume the pattern holds", and I also can't imagine they wanted you to test the 100 case, or provide an inductive proof (puke). In an interview I would say: Intuitively, 50/50. If the first person picks their seat or my seat (equally likely), it is decided that I do or do not get my seat immediately, and if they pick a middle seat, the same argument applies to the person whose seat they take -t hey either take my seat or their seat with equal probability, or reduce the question to a smaller case.
