That logic should work for n = 3, 4, but it doesn’t. Since there’s nothing in there dependent upon the constant 100, I don’t buy it.
Not sure what you mean ultrafilter.
Let’s take n = 4.
Case 1. The odds of him sitting in his assigned seat is 1/4.
Case 2. The odds of him sitting in your assigned seat is 1/4.
Case 3. = (3/4) * (2/3) * (1/2) = 1/4.
There can be at most 1 passenger that hasn’t sat down whose seat is taken. By definition, if a person is sitting down, their actual seat is occupied, with the exception of the first passenger. Once the first passenger’s seat is filled, there is a 100% chance that you’ll be able to sit in your own seat.
Still working on the math, though…
Thanks, I will check my program for an error.
Ah, let me think about Punoqllads’s assertion that someone may take the first passenger’s seat thereby canceling the first passenger’s action.
I’d rather do the case n = 3, cause there are fewer possibilities. The first guy is supposed to sit in seat 1, and you’re supposed to sit in seat 3.
The possible outcomes are as follows, where the item in the ith position indicates where passenger i sits:
1, 2, 3
2, 1, 3
2, 3, 1
3, 2, 1
Note that in exactly half of those, you end up sitting in your own seat.
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?
Not sure if this is helpful, but the idea that someone else cancels the first passenger’s action by taking his seat seems somewhat recursive.
Enumerate the passengers according to the order that they line up. Suppose passenger 1 takes the seat of passenger k. Now, passengers 2 through k-1 will take their own seats. Consider what happens if we “reassign” passenger k the seat of passenger 1. It’s as if passenger k “lost his ticket”, and now decides to randomly choose a seat. So the problem is reduced from n to n - (k-1).
I am not sure if this is helpful in computing the probabilities.
Here’s one attempt at a solution.
Let A be the event that you get your seat, B be the event that the first passenger sits in his own seat, C be the event that he sits in some other passenger’s seat, and D be the event that he sits in your seat. The function we’re interested in is P[sub]n/sub, the probability that you sit in your own seat on an airplane with n passengers.
By the basic rules of conditional probability, P[sub]n/sub = P[sub]n/subP[sub]n/sub + P[sub]n/subP[sub]n/sub + P[sub]n/subP[sub]n/sub. I think it’s pretty clear that P[sub]n/sub = 1, P[sub]n/sub = 0, P[sub]n/sub = 1/n, and P[sub]n/sub = (n - 2)/n. So that gives us P[sub]n/sub = 1/n + (n - 2)/n * P[sub]n/sub.
Now, it’s clear that P[sub]2/sub = 1/2. If it’s reasonable to claim that P[sub]n/sub = P[sub]n - 1/sub, then you can use induction to show that P[sub]n/sub = 1/2 for n > 2. The only question is whether that last claim is reasonable. I believe that it is, but I need to think about it.
Instead of “If any passenger after the first …” I should have said “If any passenger …”
Xema , I believe you have found the “simple trick” that I was expecting for this problem. I think that argument works very well and it matches it up with the answer I am getting from my corrected computer program.
Thanks.
I think this is the solution. I was about to post the same thing when I saw your post. Essentially, since it is random where people sit if “bumped” from their seat, there is no reason to assume that there is a higher probability of someone choosing seat F over seat Y, or vice versa. So, when your turn comes, the probability of seat F being occupied is the same as the probability of seat Y being occupied, and since those are the only possibilities when your turn comes, each has a probability of 50%.
Looking back at jawdirk’s original post, this is exactly what he said also.
The probability that the first guy sits in your seat is 1/n, in which case you will not get your seat. The probability that he sits in his own seat is 1/n, in which case you will definitely get your seat. The probability that he sits in neither his own seat or your seat is (n-2)/n. In this case, suppose he sits in passenger k’s seat. Passengers 2 through k-1 will sit in their own seats, and the problem reduces to the case where there are n - (k-1) passengers. Inductively assume that the probability that you will get your own seat when there are fewer than n passengers (but more than 2, of course) is 1/2. Then, the probability that you will get your seat when there are n passengers is
1/n + (n-2)/n = (1+n/2-2/2)/n = 1/2
Does it? In the case of n - (k - 1) passengers, the first person could pick their own seat. The kth guy, who’s the first guy whose seat is taken, can’t. I’m getting hung up on that difference.
I am considering the case where passenger 1 takes passenger k’s seat. Then, passengers 2 through k-1 take their own seats. So the set of seats we are left with the seats of passengers k+1 through n and the seat of passenger 1. Now, if we simply reassign passenger k to the seat of passenger 1, doesn’t that reduce the problem to a smaller case.
The recursion should work, I think:
The first passenger can take one of the two special seats, or not. If he takes a special seat, the odds are 50-50. If he does not take a special seat, then he takes the seat of passenger X. In this case, the passengers up to number X get on the plane and take their seats, and then X has the same situation as the original passenger, but with fewer seats.
At some point before the last person gets on the plane, one of the other passengers must have chosen a special seat, because there’s only the single seat left.
Here is the math:
For every passenger n, n belongs to 2 through 99, there are two possibilities:
A. His seat will be empty, and he will take it. This does not influence your chances of getting your seat.
B. He will have the choice of seat #1, seat #100, or seat #n+1 through #99.
If he picks #1, you get your seat.
If he picks #100, you don’t get your seat.
If he picks any other seat #x then passenger x will have choice B. and passenger n+1 through x-1 will have choice A.
Note that the chance of #1 and #100 are equal.
Passenger 1 is just like 2 through 99, except he always has choice B.
Therefor, all passengers, 1 through 99, either do not influence your chances, or have an equal chance of giving you your seat, or taking it from you.
Therefor, in sum, your chances of getting your seat, or having it taken from you must be equal.
Since only one empty seat remains when you board the plane, the chances must be 50-50.
Ah, that does work.
If I make B the event that the current passenger sits in the seat belonging to the first passenger, it works.
This is probably not scientific or even mathematic, but since it’s been over 25 years since I did probabilty, I went at it the hard way. I made a 10x10 grid numbered 1-100 and a copy of that cut into 100 pieces (hey, I’m bored).
I put the pieces in a bag and mixed them up. I took out one piece and put it aside without looking at it. This represents the first guy who dropped his ticket. I then marked off a square at random. I started pulling out pieces and marking the spot on the grid. When I pulled a piece already chosen at random, I would choose another spot at random and continue.
After three runs:
1st: The last person got their assigned seat while 6 didn’t
2nd: The last person got their assigned seat while 5 didn’t
3rd: The last did not get their assigned seat as well as 5 others
What does this mean? Beats me.