I came across this problem a few weeks back. Couldn't solve it.
There are 100 people waiting in a queue waiting to enter a movie theater. The theater has exactly 100 seats numbered 1 to 100. The first person in the queue enters and chooses any seat he likes and sits there. The n-th person in the queue, where n can be 2,3,...100, enters the theater after the (n-1)-th person is seated. He sits in seat no. n if he finds it vacant; otherwise he takes up any unoccupied seat. Find the total number of ways in which 100 seats can be filled up provided the 100-th person occupies seat no. 100.