# Wasted a bit of time on this but still failed to come up with a solution.Help!!

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$.

6 years, 5 months ago

This discussion board is a place to discuss our Daily Challenges and the math and science related to those challenges. Explanations are more than just a solution — they should explain the steps and thinking strategies that you used to obtain the solution. Comments should further the discussion of math and science.

When posting on Brilliant:

• Use the emojis to react to an explanation, whether you're congratulating a job well done , or just really confused .
• Ask specific questions about the challenge or the steps in somebody's explanation. Well-posed questions can add a lot to the discussion, but posting "I don't understand!" doesn't help anyone.
• Try to contribute something new to the discussion, whether it is an extension, generalization or other idea related to the challenge.

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold
- bulleted- list
• bulleted
• list
1. numbered2. list
1. numbered
2. list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1paragraph 2

paragraph 1

paragraph 2

[example link](https://brilliant.org)example link
> This is a quote
This is a quote
    # I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
MathAppears as
Remember to wrap math in $$ ... $$ or $ ... $ to ensure proper formatting.
2 \times 3 $2 \times 3$
2^{34} $2^{34}$
a_{i-1} $a_{i-1}$
\frac{2}{3} $\frac{2}{3}$
\sqrt{2} $\sqrt{2}$
\sum_{i=1}^3 $\sum_{i=1}^3$
\sin \theta $\sin \theta$
\boxed{123} $\boxed{123}$

Sort by:

I 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

- 6 years, 5 months ago

Excellent job!!I think this is the perfect solution!!

- 6 years, 5 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}$

- 6 years, 5 months ago

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

Staff - 6 years, 5 months ago

I have another solution! :)

- 6 years, 4 months ago

- 6 years, 4 months ago

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.

- 6 years, 5 months ago

"Otherwise he takes an unoccupied seat" meaning he choses it at random?

Staff - 6 years, 5 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?

- 6 years, 5 months ago

Yes sir, that's how it is?

- 6 years, 5 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.

Staff - 6 years, 5 months ago

No sir, thequestion asks for the number of ways only ..not the probability

- 6 years, 5 months ago

Another question to ponder is the probability that the last seat is free for person 100 to take. This is probably an easier question to tackle.

- 6 years, 5 months ago