Probability "Brain Teaser" [duplicate]

Question

I came across a "brain teaser" which goes like this:

Bruna was first to arrive at a 100 seat theatre. She forgot her seat number and picks a random seat for herself.

After this, every single person who get to the theatre sits on his seat if its available else chooses any available seat at random. Neymar is last to enter the theatre and 99 seats were occupied.

What's the probability what Neymar gets to sit in his own seat?

The solution was $1/2$, their reasoning being that there are two possibilities, Neymar either gets his seat or not. This seems very flawed thinking to me because nothing says the two possibilities have equal probability.

I calculated it as $1/100 + 1/99$, but I think this is still wrong.

My reasoning was there are two scenarios which result in Neymar's seat being available, either:

• Bruna sits in the right seat in which case everyone also sits in their correct seat, this has a $1/100$ chance; or,
• Bruna sits in the wrong seat and there's a $98/99$ chance it is not Neymar's seat, then the next person has a $97/98$ chance of not sitting in Neymar's seat, and so on. Which gives $98!/99!$ or $1/99$.

My confusion lies in the fact that the subsequent people in the second scenario do not always take their seat at random, they only select a random seat if their seat is occupied.

How would I go about solving something like this?

Answer 1

The sample space of the last passenger, consisting of all possible free seats, has only two elements. Either the seat intended for the first passenger is free or the last passenger’s seat is available. The reason is, that if another seat is not occupied, it was also not occupied when the passenger with that seat number entered the plane. Hence it would be occupied by that passenger. Consequently, only the first and last passengers’ seats can be free. The experiment would not be affected, in particular the behavior of the first 99 passengers would not be affected, if we switch the tickets of the first and last passengers. So, the last passenger’s seat will be free with the same probability as in the original experiment The last passenger’s seat will be free in either the original or the adapted experiment. As the probabilities are equal and add up to one. The probability is a half.

Answer 2

The Nigel Overmars' symmetry argument is very elegant, but there is also a simple way to compute the probability through the following idea: any occurrency is accounted by something like: $$ 1 \to n_1 \to n_2 \to \ldots \to n_k \to 1 \tag{1}$$ denoting that person $1$ (Bruna) seats in the place of $n_1>1$, person $n_1$ seats in the place of $n_2>n_1$, $\ldots$, person $n_k$ seats in the place of Bruna. The probability of any event like $(1)$ is $$\frac{1}{100}\cdot\frac{1}{101-n_1}\cdot\ldots\cdot\frac{1}{101-n_k}$$ and there are $\binom{99}{k}$ events like $(1)$ - one for every choice of $k$ distinct numbers in $[2,100]$.

The probability that $k+1$ people do not seat in their place is so the coefficient of $x^k$ in the product: $$\frac{1}{100}\prod_{m=2}^{100}\left(1+\frac{x}{101-m}\right)=\frac{1}{100}\prod_{n=1}^{99}\left(1+\frac{x}{n}\right)$$

Neymar finds his place free (event $F$) iff Bruna sits in her place ($1\to 1$) or $100$ does not belong to the set $\{n_1,\ldots,n_k\}$, hence:

$$\mathbb{P}[F]=\frac{1}{100}+\frac{1}{100}\sum_{k=1}^{99}[x^k]\prod_{n=2}^{99}\left(1+\frac{x}{n}\right)=\frac{1}{100}\prod_{k=2}^{99}\left(1+\frac{1}{n}\right)=\frac{1}{100}\cdot\frac{100}{2}=\frac{1}{2}.$$

Answer 3

Let seat m be the seat of the person who enters m-th.

Bruma picks seat m' and doesn't disrupt the picking until the m'-th person enters. This person can then pick a seat > m' or can pick Bruma's seat < m', if he does this, the disruption ends. If not, the same reasoning applies for the m''-th seat.

If the 99-th person can't pick his seat, that person can sit on Neymar's or on Bruma's seat. If the 99-th person can pick his seat, Neymar can pick his seat if the disruption has ended i.e. some <99-th person picked Bruma's seat and can't pick his seat if that <99-th person picked his seat.