Seats on a plane [duplicate]

Question

200 people are waiting to board an airplane with 200 seats, one person at a time. The first person to get on the plane has lost his boarding pass, so he sits in a random seat. The second person does the following: Goes to his seat (the one it says to go to on the boarding pass). If unoccupied, sit in it. If occupied, find a random seat to sit in. Everyone else behind him does the same. You are the last person to board the plane. What is the chance that you get to sit in your assigned seat?

Answer 1

Let $\pi$ be the permutation of $1 \ldots 100$ such that for $i = 1 \ldots 99$, $\pi(i) = j$ where passenger $i$ took the seat assigned to passenger $j$, and $\pi(100)$ is the number of the passenger who was assigned the last vacant seat. In the disjoint cycle decomposition of $\pi$, let $(100, c_2, \ldots , c_m)$ be the cycle containing $100$. If that cycle is just $(100)$, Bob finds his own seat vacant, else he displaces passenger $c_m$, who displaces passenger $c_{m-1}$ and so on down to passenger $c_2$ who gets the vacant seat. Thus the people displaced are exactly the others in the cycle containing $100$.

For $1 \le m \le 100$, there are $99!/(100-m)!$ ordered $m$-cycles containing $100$. Given such an $m$-cycle, there are $(100-m)!$ possible permutations of the other $100-m$ seats. Thus the probability that $100$ is in an $m$-cycle is $99!/100! = 1/100$ for each $m$ from $1$ to $100$. Given that it is is an $m$-cycle, the probability that $1$ is in this $m$-cycle is $(m-1)/99$. Thus the total probability that Alice is displaced, i.e. that $1$ is in the cycle containing $100$, is

$$ \sum_{m=1}^{100} \dfrac{m-1}{9900} = \dfrac{1}{2}$$

Answer 2

There is a $\frac 1{100}$ chance that Bob is left with his assigned seat and no one has to move. If this is not the case, the person displaced by Bob has a $\frac 1{99}$ chance of finding his assigned seat unoccupied, since the unoccupied seat cannot be Bob's. The next person has a $\frac 1{98}$ chance of finding his seat unoccupied, and so on. In general the probability that exactly $n$ people will be displaced is the probability of the first $n-1$ people (including Bob) not finding their seat unoccupied multiplied by the probability of the $n$th passenger finding his assigned seat empty.

$$P(n)=\frac 1{100-n}\prod_{i=0}^{n-1}\frac {99-i}{100-i}$$

Conveniently, the product telescopes to a simple ratio.

$$P(n)=\frac 1{100-n}\left(\frac{99}{100}\frac{98}{99}...\frac{101-n}{102-n}\frac{100-n}{101-n}\right)=\frac 1{100}$$

It is clear that Bob has an equal likelihood of displacing each of the $99$ other passengers. The person displaced also has an equal likelihood of displacing the remaining $98$, and so on. In general, if $n$ people are displaced, the probability that Alice is one of them is $\frac n{99}$. We can therefore take the sum of this probability over all possible values of $n$.

$$P(Alice)=\sum_{n=0}^{99}\frac 1{100}\frac n{99}$$

$$P(Alice)=\frac 1{9900}\sum_{n=0}^{99}n$$

$$P(Alice)=\frac 1{9900}\frac{(99)(99+1)}{2}=\frac 12$$

Thus there is a $\frac 12$ chance of Alice needing to move. Interestingly, this result does not depend on the number of passengers on the plane.

Answer 3

It suffices to calculate the probability that, for a permutation in $S_{100}$, we have that $100$ and $1$ belong in the same cycle. (See Robert Israel's excellent answer for why.) To do so, we try to construct the cycle $100$ belongs in.

Starting from $100$, there is a $1/100$ chance that $100$ is sent to itself, thus ending the cycle. There is also a $1/100$ chance that $100$ is sent to $1$, and it doesn't matter what the rest of the cycle is. There is a $98/100$ chance that $100$ is sent to something else.

In that case, there is a $1/99$ chance that the second number is sent to $100$, thus ending the cycle, and a $1/99$ chance that it is sent to $1$ instead, leaving a $97/99$ chance of being sent to some third number.

In general, if the cycle has not finished cycling and does not contain $1$ after $i$ steps, then the $(i+1)$th number has an equal probability $1/(100-i)$ of being sent to either $1$ or $100$. Thus, the probability that the cycle containing $100$ does contain $1$ (i.e. the cycle sends some number to $1$) and the probability that it does not contain $1$ (i.e. the cycle sends some number back to $100$ before $1$) must be equal, and since one of them must occur, their probabilities must be $\boxed{\frac{1}{2}}$.

In particular, note that $100$ can be replaced by any integer $n\ge 2$ and the same result holds.

Answer 4

Consider the 3 options.

Alice sits in her own seat. Alice sits in Bob's seat. Alice sits in some other persons seat.

If Alice sits in her own seat she will not be asked to move. If alice sits in Bob's seat she will. If Alice sits in a third seat it isn't determined.

So for the probability Alice will have to move or not are even (1 percent each).

If Alice sits in person C's assigned seat, consider which seat C chose to sit in. C has the same three options. Alice ' s seat; Bob's seat or person D's seat.

The probability C will choose alice ' s is the same as the probability she will choose Bob's

Keep this chain going. C displaces D; D displaces E. And so on. Eventually you will come to some person Q who finally does choose Alice ' s or Bob's seat.

Let Q be the first person in the chain who chooses either Alice ' s or Bob's seat. (Q could appear as early as Alice herself, or as late as the 99th person on the plane).

If Q chooses to sit in Alice ' s seat, Alice will not have to move-- the loop Alice to C to D .... to Q to Alice is a closed loop. The only person who can ask anyone to move would be the next person in the loop. Bob is not on the loop so no-one will be asked to move.

If Q chooses to sit in Bob's seat Alice will move. Q will ask P who asks the person previously on the chain down to Alice.

The probability that Q (whoever he or she is) is equally likely to choose to be Bob's or Alice's. So the probability that Alice must move is exactly 1/2.