# There are 100 people in a queue waiting to enter a hall. The hall has exactly 100 seats numbered from 1 to 100. The first person in the queue…

There are $100$ people in a queue waiting to enter a hall. The hall has exactly $100$ seats numbered from $1$ to $100$. The first person in the queue enters the hall, chooses any seat and sits there. The $n$-th person in the queue where $n$ can be $2,\ldots,100$, enters the hall after $(n-1)$-th person is seated. He sists in seat number $n$ if he finds it vacant; otherwise he takes any unoccupied seat. Find the total number of ways in which $100$ seats can be filled up, provided the $100$-th person occupies seat number $100$.

I could not realise how this chaotic behaviour will end. I think the solution lies in finding that. Please help.

-
Hint: Try it first for small number of people. For example for 4 people there are 4 ways in which 4 seats can be filled up, provided the 4-th person occupies seat number 4. – mcihak Feb 20 '14 at 15:24
I am counting 5. – hunter Feb 20 '14 at 15:36
There are four: Suppose the people are A, B, C, and D. They can end up in these ways: ABCD, BACD, CABD, CBAD. Note that the other two arrangements with D last (ACBD, BCAD) are impossible, because when it was person B's turn to sit, seat #2 was unoccupied but s/he didn't sit there. – Steve Kass Feb 20 '14 at 16:54
possible duplicate of Taking Seats on a Plane – Steven Stadnicki May 8 '14 at 4:29

Let $s_r$ be the number of the seat taken by the $r^{th}$ person.

Suppose $s_1=k_1$, then person $k_1$ is the first to find their seat already filled. Either person $k_1$ takes seat $1$, when the remainder of the passengers take their own seat, or $s_{k_1}=k_2\gt k_1$. Person $k_2$ is the second person to find their seat occupied (repeat the argument).

So you need to count the number of increasing sequences $2\leq k_1\lt \dots \lt k_r\le 99$ where $k_r$ indexes the people who find their seat occupied and have to occupy a seat other than their own.

To compute the count note that any number between $2$ and $99$ inclusive can either be in the sequence or out of it. So that comes to $2^{98}$.

The normal question about this situation is to find the probability that the $100^{th}$ person sits in their own seat. If this is part of your method for solving that, it is not the easiest way of getting an answer.

-

I think I have a sketch, but I haven't worked out all the details, and so I am not 100% sure. Some hints below.

Hint:

• For your decision it's not important who took your seat, only that it is taken and how many are left.
• In turn $k$ seats $2,3,\ldots (k-1)$ are taken (by whoever sits there).
• The additional taken seat is random.
• If the 100th person occupies seat number 100, then nobody ever had picked this place. In other words this seat could have been nonexistent at all.

I hope this helps $\ddot\smile$

-

Note Mark's comment: This counts the number of ways without the final condition that person 100 sits in seat 100. The correct answer is $2^{98}$; assign seat 100 to person 100 first, then proceed as I describe below. When you get to seat $99$, there will be 1, not 2 possibilities.

I might be missing something, but I think the following argument shows that there are $2^{99}$ ways to do this.

First, note that where $k>1$, seat $k$ must be occupied by one of the first $k$ people. Now enumerate the seat assignment possibilities by going through the seats from seat $2$ to seat $100$ first. (All we need to do here is count the number of arrangements, so as long as we find them all, it doesn't matter if we generate them by a different process than the one in the problem.) There are two ways to fill seat $2$ (person $1$ or person $2$). No matter who fills seat $2$, there are then $2$ ways to fill seat $3$, since it must be filled by one of the first three people not in seat $2$. And so on, so there are $2^{99}$ ways to fill seats $2$ through $100$. The remaining person sits in seat $1$, so there is only one choice for the final seat assignment.

-
Note the condition that person $100$ sits in seat $100$ which reduces the number by a factor of $2$. – Mark Bennet Feb 20 '14 at 16:13

The correct answer is 99! Check it out for 4 people. This is an application of funtions. i.e No. of one-one functions when co-domain(No. of seats) and domain(passengers) are equal.

-
Absolutely not! The correct answer is $2^{98}$ which I have already gotten from several confirmed sources just like other answer givers of this question. I just don't feel like explaining and downvoting this answer. – Hawk May 8 '14 at 9:54