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,3,...100\) enters the hall after the \((n-1)\)-th person has seated. He seats in seat number \(n\) if he finds it vacant; otherwise he takes an unoccupied seat at. Find the total number of ways in which the \(100\) seats can be filled up, provided the \(100\)-th person occupies seat number \(100\).

## Comments

Sort by:

TopNewestI think I have a solution. Let \( P_{i} \) denote person \( i \) and \( S_{i} \) denote seat \( i \). Also, let \( P_{i} = S_{j} \) denote that person \( i \) sits in seat \( j \). Firstly we will prove a lemma (L1): 'If \( P_{i} = S_{j} \) then either \( j \geq i \) or \( j = 1 \)' To show this, let us assume that in fact \( j < i \) and \( j \ne 1 \). Consider \( P_{i} \) is just about to enter the hall. \( P_{i} \) can only sit in \( S_{j} \)if \( S_{j} \) is empty at this time. But if \( S_{j} \) is empty at this time then \( S_{j} \) was also available when \( P_{j} \) entered the hall (since \( P_{j} \) entered the hall before \( P_{i} \)). Therefore \( P_{j} \) would have sat in \( S_{j} \), and so in fact \( S_{j} \) would not be empty when \( P_{i} \) was about to enter the hall. Therefore we have a contradiction, so our assumption that \( j < i \) and \( j \ne 1 \) was false, so either \( j \geq i \) or \( j = 1 \) (\(j = 1 \) is allowed since \( P_{1} \) is not compelled to sit in his own seat like everyone else is). So the lemma is proved. So now, say that \( P_{a} = S_{b} \) where \( a \ne 1 \) and \( a < b \). This means that \( S_{b} \) is occupied when \( P_{b} \) is about to enter the hall. Therefore, using L1, \( P_{b} = S_{c} \), where \( b < c \). This is forming what will be known as a series ( \( a,b,c,... \)). However, we now have the same problem with \( P_{c} \), ie. \( P_{c} = S_{d} \) where \( c < d \). This would seem to imply that if someone other than \( P_{1} \) sits in a seat which is not their own then it will form an infinite increasing series, but we only have finitely many people. However, we have forgotten that someone in the series can sit in \( S_{1} \).

Clearly only 1 person can sit in \( S_{1} \), and we have just seen that a series is only possible if someone in the series does sit in \( S_{1} \). Therefore there can only be at most 1 series. Therefore, if there is a series, \( P_{1} \) must be part of it, since someone else will be sitting in his seat, and so \( P_{1} = S_{m} \) where \( m \ne 1 \), but if \( m \) were not part of the series then we would have started a second series, which we know is not allowed, so \( m \) is part of the series and therefore so is \( P_{1} \). Since \( P_{100} = S_{100} \) we know that \( 100 \) is not part of the series, and from the work we have just done we know that \( 1 \) is definitely part of the series (if there is one). So in fact we are done: The number of ways to fill 100 seats with the given conditions is the same as the number of strictly increasing sequences we can choose from the set \[ {2,3,4,...,99} \] where the empty set is valid (since this corresponds to when there is no series - everyone sits in their own seat). To make this a bit more clear I will give a random example. Say we pick the strictly increasing sequence \[ {14,23,97} \] Then this corresponds to: \[ P_{1} = S_{14} \] \[ P_{14} = S_{23} \] \[ P_{23} = S_{97} \] \[ P_{97} = S_{1} \] and \( P_{i} = S_{i} \) when \( i \ne 1,14,23,97 \). Every selection of numbers from the set can be ordered only 1 way so that it is strictly increasing. Therefore the answer is : \[ \displaystyle\sum_{k=0}^{98} \dbinom{98}{k} = 2^{98} \]

If anyone has any queries or questions please feel free to ask – Josh Rowley · 2 years, 11 months ago

Log in to reply

– Eddie The Head · 2 years, 11 months ago

Excellent job!!I think this is the perfect solution!!Log in to reply

– Josh Rowley · 2 years, 11 months ago

Thanks. I noticed after doing my solution that there is a nice problem (and result) which follow naturally: What is the probability that \( P_{a} = S_{a} \) if \( a \ne 1 \)? Well, if \( P_{a} = S_{a} \) this means that \( a \) is not in the series. Therefore we in fact can only choose from 97 numbers not 98 for our strictly increasing sequence, and so there are \( 2^{97} \) possible combinations if \( P_{a} = S_{a} \). Therefore the probability that \( P_{a} = S_{a} \) is \( \dfrac{2^{97}}{2^{98}} = \dfrac{1}{2} \). So the probability that someone sits in his own seat (provided that person isn't \( P_{1} \)) is \( \dfrac{1}{2} \)Log in to reply

– Paramjit Singh · 2 years, 11 months ago

I have another solution! :)Log in to reply

– Eddie The Head · 2 years, 11 months ago

Please share!! :)Log in to reply

– Calvin Lin Staff · 2 years, 11 months ago

Indeed. This is the version that I'm more familiar with, which is why I asked if the probability was "at random".Log in to reply

Another question to ponder is the

probabilitythat the last seat is free for person 100 to take. This is probably an easier question to tackle. – Daniel Liu · 2 years, 11 months agoLog in to reply

"Otherwise he takes an unoccupied seat" meaning he choses it at random? – Calvin Lin Staff · 2 years, 11 months ago

Log in to reply

– Eddie The Head · 2 years, 11 months ago

Yes sir, that's how it is?Log in to reply

– Calvin Lin Staff · 2 years, 11 months ago

I previously thought you were asking for the probability, which is why I asked if it was "at random'. But given that you're asking for the number of ways, that doesn't matter then.Log in to reply

– Eddie The Head · 2 years, 11 months ago

No sir, thequestion asks for the number of ways only ..not the probabilityLog in to reply

– Finn Hulse · 2 years, 11 months ago

Yes. And whatever he chooses creates a whole different set of configurations. Which is why this problem is annoying. Also, are you following me?Log in to reply

Holy crap. I just tried it for half an hour, thought it was easy, and then realized that you have to consider HUGE amounts of cases. I think, though, it would be cool to say that there are 10 people, and write a problem like that. I'll do that, actually. – Finn Hulse · 2 years, 11 months ago

Log in to reply