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

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

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.

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

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.