Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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 at 15:24
    
I am counting 5. –  hunter Feb 20 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 at 16:54
    
possible duplicate of Taking Seats on a Plane –  Steven Stadnicki May 8 at 4:29
    
@StevenStadnicki I think not...the problem you linked is about probability, and the question I asked is about number of arrangements. Please reconsider. –  Hawk May 8 at 9:55

4 Answers 4

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.

share|improve this 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$

share|improve this answer

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.

share|improve this answer
2  
Note the condition that person $100$ sits in seat $100$ which reduces the number by a factor of $2$. –  Mark Bennet Feb 20 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.

share|improve this answer
1  
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 at 9:54

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.