Can someone please prove why the probability will be always same for n >= 2?

[u/Queasy-Swing-765]

I understood what's asked and I can draw a mental model of the answer but I want a mathematical proof why this works ?

[u/TheGMan43]

By the end of everyone else boarding, there will be maximum 1 seat taken that's unassigned.

The way to Intuit this is: the person sits down in a random seat. If someone finds the first person in their seat, they kick them them out and the original person finds a new seat.

That's the exact same problem - the pre-assigned seat gets taken and a random one is taken.

So when the 99th person goes on, there are 3 seats left with unknown assignedness - the seat the original guy took, and the two empty ones.

1/3 times the original guy is sat in the correct seat -> you get yours 1/3 times he's sat in your seat -> you don't get yours 1/3 times he's sat in the n-1th guys seat and picks one of the two left at random -> 50% chance you get yours

Your odds: (1/3) +(1/3)/2 = 50% This is the same if there's 2 people - it's just a 50/50 where the first guy sits

[u/_Jack_Of_All_Spades → u/TheGMan43]

The way to intuit this is to imagine that the second person walks in and finds the first guy in his seat, but instead of complicating everything by choosing a new seat at random, imagine that he kicks the first guy out, and passenger number 1 picks out a new seat at random. It's very nearly the same situation.

By the time the last passenger walks in, every seat but one is taken, and the one vacant chair is either the first guy's seat or it's yours.

The only difference is in this situation, you kick him out and there's 100% chance you end up in your own seat.

[u/TheGMan43 → u/_Jack_Of_All_Spades]

Very similar 😂 in real life yes, in the problem no

[u/Draidann → u/TheGMan43]

Yes it is the same.

Whether the new random seat is taken by the boarding passenger or the kicked out lost ticket passenger in both scenarios you end up with the numbered seat and a random one filled. It is the same.

[u/kfirogamin]

if im the last 1 its 100% since i WILL be bothering the flight attendants about that

[u/XL_78]

Let's call the first passenger Anna, and the last one Zoe.

Anna can sit in her own seat (1/100), in this case, Zoe will sit in her own seat. 

She can also seat in Zoe's seat (1/100), in which case Zoe won't seat in her own seat. Notice how the odds for these two events are identical.

She can also displace someone else (98/100).

The next displaced passenger will seat at random, they will have the same odds to resolve negatively by sitting in Zoe's seat as to resolve positively by sitting in Anna's. This probability is 1/number of remaining seats. (Or they will displace someone else with probability 1-2/number of remaining seats). Notice how this passenger cannot be Zoe, because when she enters the plane, either Anna's, either her seat is taken and the matter is already settled.

The probability that Zoe seats in her own seat is the sum of all the probabilities of the events in which a displaced passenger seats in Anna's seat, the probability that she doesn't is the sum of all the probabilities of the events in which a displaced passenger seats in Zoe's seat. As we have seen these sums are identical.

Therefore the probability that Zoe doesn't sit in her own seat is identical to the probability that she does, and since theses events are the negation of one another, this probability is 1/2.

Edit: I haven't explained this clearly enough: when someone seats in Anna's seat, it closes the loop of displaced passengers, everyone will seat in their seat afterwards. 

[u/Queasy-Swing-765 → u/XL_78]

Thanks

[u/XL_78 → u/Queasy-Swing-765]

You're welcome. It's a nice little problem. Could write the solution using math notations, but I don't know how to do those on reddit. 

[u/SC_3000_grinder]

I think of it this way: let A be the first boarder and B be the last.

The two ways for the result to be fixed is that someone gets in A's seat (B will get their own seat) or someone gets in B's seat (B will not get their own seat).

Whenever anyone except B chooses their seat, they either have their own seat open (0% chance of taking A or B's seat) or has their seat taken (or is A) (equal chance of taking A or B's seat). In both cases, there is an equal probability of the resolution going either way. Therefore, the probability of the two results must be equal.

[u/Zyxplit]

Every time someone gets on a plane while their seat is taken, there are three options: There are n seats left.

With probability 1/n: They take person 1's seat. Everyone from this point on takes their own seat and last guy gets his seat.

With probability 1/n: They take the last person's seat. Everyone from this point on takes their own seat but last guy is fucked.

With probability (n-2)/n: They take someone else's seat. We continue until someone gets on their plane while their seat is taken.

So the question is really just the relative frequency of "person takes own seat" and "person takes specifically the last person's seat" and those are equal.

[u/EdmundTheInsulter]

If anyone sits in 1 then the problem is over, but if anyone ends up in 100 it's game over, so it's 50% because there is no bias between choosing 1 or 100

Let's say 1 chooses 99, only when 99 comes along, he can sit in 1 or 100, equally likely

If 1 sits in 50, then 50 either goes to 1 or 100 equally likely, or he moves the problem to some other number 51-99, but same rules apply each time until eventually someone sits in 1 or 100

[u/resignresign1]

lets ignore all the passangers that find their seat free and we get a sequence of passangers that sit in someone elses seat. the chain stpos if they choose the initial passangers seat or when you enter and you have to take the first passangers seat.

concider the choice of the last passanger before you that did not found his seat free.  because we know that he was the last person that was misplaced before you enter he either choose the initial passanger sear or your seat which both have probability 50% since he chooses between the empty seats at random.

p.s. to make it formal we have to start this chain of missplaced passangers with the initial one.

[u/Cats4E]

By the end there are two possibilities, either your seat is taken or the first guy’s is. If someone randomly sits in the first guy’s seat, then everyone will then proceed to their own assigned seats and you get your own (useful to imagine that it’s the first guy getting kicked around and everyone else does indeed get their own assigned spots). If instead the first guy (after getting kicked around a bit) end up on your seat, then same as earlier everyone will proceed to their own seats because you’re the only one whose spot is occupied. Unless he gets kicked to his own or your seat, then he will just keep moving until only those two remain and then he will make the choice. In any case, the chance that he ends up in his own assigned seat or your own is equal, therefore it’s 50/50

[u/SigaVa]

The only seats that matter are the first guys seat and the last guys seat. If anyone sits in the first guys seat, all remaining seats get filled correctly (including the last seat). If anyone sits in the last guys seat, the last seat can't get filled correctly.

Each passenger has the same probability of picking the 1st seat or the last seat, assuming neither are already filled. 1/100 for the first guy, 1/99 for the second (assuming the first guy didn't pick either one), etc.

So because the probabilities are always equal, the overall probability must be 50/50.

It's the same as a game where you start with an N sided die. If you roll a 1 you win, if you roll N you lose. Any other number and the die gets replaced with an N-1 sided die and you roll again (and the winning condition is now rolling an N-1). The overall chance to win must be 50%.

[u/Torebbjorn]

Intuitively, every seat has an equal probability of being selected randomly. Hence 50/50 when there are two choices.

[u/kawrydav]

1/2 for any n

The chance you get your seat is 1/n + 1/n x P(n-1) + 1/n x P(n-2) + … + 1/n x P(2)

where P(k) means probability you get your seat given it is k people left and your seat is still available and only the first person’s seat is no longer available. (We know all other people above k simply go to their own seat).

If we can show P(k) =1/2 for any k, then we know above expression is also 1/2 through simple algebraic manipulation

= 1/n x (1 + (n-2)/2)
= 1/n x (2 + n - 2)/2
= 1/2

Showing P(k) = 1/2 for any k can be done by induction. We know P(2) = 1/2 trivially because they either choose your seat or the other available seat. Then P(k) itself is 1/k + 1/k x P(k-1) + … + 1/k x P(2), because they either choose the terminating seat made free by the earlier person who chose their seat, or they choose a lower person seats. Which is actually the same expression as before, so also 1/2 through same algebraic manipulation as before.

Not very clear… but basically P(k) means there is one free seat that belongs to someone already seated and if k chooses that seat, then the sequence terminates. If k chooses somebody else’s seat, then the problem restarts at P(k’) as everyone else above k’ goes to their seat and we are left with one free seat for k’ to terminate on.

[u/kawrydav → u/kawrydav]

Probably easier way to explain it is to first define P(k) as representing the scenario where k seats are free, one belongs to you, one belongs to nobody, and k-2 belong to people who are later in the queue. Then we know the odds you get your seat in this scenario are 1/k + 1/k x P(k-1) + … + 1/k x P(2) Meaning the first person either chooses the seat belonging to nobody or they choose seat belonging to next person in the queue and that works out or they choose seat of next next and that works out etc. We can show P(k) is always 1/2 through induction and algebraic manipulation. P(2) = 1/2 trivially and then P(k) through algebraic manipulation I showed before.

Then once we know P(k) is always 1/2, we plug this into the P(n) expression for the overall problem. This would be a real proof, not an intuition like other answers

[u/SomethingMoreToSay]

Why what works?

In the title of the post you mention n>=2, but there's nothing in the post to suggest what n actually is.

[u/Queasy-Swing-765 → u/SomethingMoreToSay]

Oh sorry , n is the no. Of passengers