0
$\begingroup$

Assume $n$ numbered people attending a movie with $n$ numbered seats.

The people stand in a line according to their numbers and they start entering and sit down as explained: the first person enters, and chooses 1 out of the $n$ seats randomly. For every other j-th person entering the room, if the j-th seat is not occupied, he sits there, otherwise he chooses one of the other available seats randomly.

What is the probability that the n-th (the last) person is in the n-th seat?

What I assumed so far:

As I see it, if the first person chooses the first seat (with probability $\dfrac{1}{n}$), then all the other people sit in their seats and the n-th person sits in the n-th seat.

Now if the first person chooses a seat $j$, where $2 \le j \le n$, then the $j-1$ people after the first one choose their seat and the j-th person has $n-j$ available seats to choose from, and I got stuck, because it leads me to multiple options, and so on.

Would appreciate some help, thanks!

$\endgroup$
6
  • $\begingroup$ Is the source of this problem a book or class? If so, has the problem source previously studied either recursion or martingale theory? My first try, which might fail, would be recursion, only because I have never studied martingale theory. $\endgroup$
    – user2661923
    Commented Mar 3, 2023 at 17:03
  • $\begingroup$ @user2661923 it is a question in an assignment. And we have not covered neither of them when it comes to probabilities to be honest $\endgroup$
    – GreekMustard
    Commented Mar 3, 2023 at 17:05
  • $\begingroup$ Were there any similar problems presented as worked examples that led up to this problem? Usually, the problem composer's intent is that you apply already presented theory to attack the problem. So, the first challenge becomes trying to determine the problem composer's intent: what theory do you think that the problem composer wants you to apply? $\endgroup$
    – user2661923
    Commented Mar 3, 2023 at 17:08
  • $\begingroup$ The alternative simple, but tried and true approach is elbow grease. Let $~n~$ take on each of the values in the set $\{2,3,4,5,6\}.$ For each value of $~n,~$ compute a final answer, keeping all of your partial analysis (for each value of $~n~$) in a very well organized manner. Then, look for a pattern in the data. Assuming that the problem composer is not deranged or sadistic, this approach should uncover a pattern in the data that will be routinely generalizable, to a function of the variable $~n.$ $\endgroup$
    – user2661923
    Commented Mar 3, 2023 at 17:14
  • $\begingroup$ @user2661923 it is basically an assignment of a different course and it’s just some kind of a brief over all calculus courses. We have literally just had one class. So everything is basically legal to use. I am not sure I know what exactly should I apply here, but we have not covered recursion nor martiangle theorem $\endgroup$
    – GreekMustard
    Commented Mar 3, 2023 at 17:15

2 Answers 2

Reset to default
2
$\begingroup$

I approached this problem from an inductive approach.

Take $E_n$ as the event that the last person in line gets his or her assigned seat when $n$ people are in the line, and put $p(n)=\mathbb{P}(E_n)$. It's easy to see how $p(1)=1$ and $p(2)=1/2$, so let's now assume that $n\geq 3$.

If $X$ is the seat taken by the first person in line, then for $k=2,...,n-1$ we have from recursion that $$\mathbb{P}(E_n|X=1)=1,\mathbb{P}(E_n|X=n)=0,\text{ and } \mathbb{P}(E_n|X=k)=p(n-k+1)$$ So with the total law, $$\begin{eqnarray*}p(n) &=& \mathbb{P}(E_n) \\ &=& \mathbb{P}(E_n|X=1)\mathbb{P}(X=1)+\dots + \mathbb{P}(E_n|X=n)\mathbb{P}(X=n) \\ &=& \frac{\mathbb{P}(E_n|X=1)+\dots + \mathbb{P}(E_n|X=n)}{n} \\ &=& \frac{1 +p(n-1)+ \dots + p(2)+0}{n}\end{eqnarray*}$$

If we take $n=3$ we can say $p(3)=\frac{1+p(2)}{3}=\frac{1}{2}$.

If we take $n=4$ we get $p(4)=\frac{1+p(3)+p(2)}{4}=\frac{1+1/2+1/2}{4}=\frac{1}{2}$.

You can use this along with induction to show $p(n)$ always equals $1/2$

$\endgroup$
2
$\begingroup$

The last person gets to sit in his own seat if and only if someone who lose his seat choose to sit in the first person's seat.

Now, any person who lose his seat is equally likely to choose the first person's seat or to choose the last person's seat. Therefore, the probability is $\frac{1}{2}$.

$\endgroup$
10
  • $\begingroup$ Could you give some further explanation regarding the first part of your answer? $\endgroup$
    – GreekMustard
    Commented Mar 3, 2023 at 17:22
  • $\begingroup$ @GreekMustard if nobody randomly choose the first person's seat, sooner or later the last person's seat will be taken by someone else who lose his seat. Therefore, in order for this last person to keep his seat, someone must lose his seat and then choose the first person's seat, and thus the rest of the people can simply sit in their own seats. $\endgroup$
    – acat3
    Commented Mar 3, 2023 at 17:26
  • $\begingroup$ To clarify the answer, if person-1 sits in seat-1 or seat-10, it is game over. Alternatively, suppose (for example) that person-1 sits in seat-6, and person-6 sits in seat-8. Then, person-6's seating was (in effect) neutral, and the question would reduce to whether person-8 game-overed into seat-1 or seat-10, or neutral-seated into seat-9. $\endgroup$
    – user2661923
    Commented Mar 3, 2023 at 17:30
  • $\begingroup$ @user2661923 I understand. For me what he wrote in the last part is proof enough that he at least tried something. Sometimes, we are just stuck and don’t know where to begin. $\endgroup$
    – acat3
    Commented Mar 3, 2023 at 17:33
  • $\begingroup$ And why isn’t in necessary to consider the other available seats other than the first and the n-th? $\endgroup$
    – GreekMustard
    Commented Mar 3, 2023 at 17:34

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .