Waste less time on Facebook — follow Brilliant.

Filling up the theater

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.

Note by Anik Chakrabarty
4 years ago

No vote yet
3 votes


Sort by:

Top Newest

Good problem! I've been thinking about it on and off and here's what I've come up with so far.

Let's start from the beginning. If person 1 sits in seat 1, he displaces no one, so everyone else sits in their respective seats (person 2 in seat 2, person 3 in seat 3, etc.). If person 1 sits in, say, seat 50, then he displaces person 50. Persons 2 through 49 sit in their respective seats, but person 50 must choose where to sit. If person 50 sits in seat 1, he displaces no one else, so persons 51 through 100 sit in their respective seats. If person 50 does not sit in seat 1, but instead, say, seat 75, he displaces person 75. Persons 51 through 74 sit in their respective seats. Person 75 must then choose whether to sit in seat 1, thus displacing no one, or one of the other seats, which displaces someone else. Of course, seat 100 is always reserved for person 100 by the problem description.

So, we see a basic pattern emerging here. For each person \( p_i \), that person can do one of three things:

  1. Sit in their respective seat \( s_i \), if available.
  2. If they can't do #1, this means that \( s_1 \) must be available. They can sit there and displace no one else.
  3. If they can't do #1, they can also sit in any seat \( s_j \) from \( s_{i+1} \) through \( s_{99} \). This will displace \( p_j \).

Special cases are \( p_1 \), who needn't do #1, and \( p_{100} \), who always sits in \( s_{100} \).

The interesting bit of the problem what I've been calling "displacement" events. When, say, \( p_{10} \) displaces \( p_{50} \), players \( p_{11} \) through \( p_{49} \) are unaffected, and sit in their respective seats. In other words, the unaffected people don't represent any choices being made. In general, only \( p_1 \) and any displaced players represent choices.

Anyway, this all suggests the following counting formula:

\( f(p) = 1 + \displaystyle \sum_{i=p+1}^{99} f(i) \)

\( f(p) \) could be thought of as the number of ways to fill the remaining seats assuming that player \( p \) has been displaced. The \( 1 \) is the case where \( s_1 \) is chosen--this gives 1 way to fill the seats, since no one else is displaced when \( s_1 \) is chosen. The summation represents the possibilities of displacing each person after person \( p \). (Of course, \( p_1 \) cannot be displaced, but \( f(1) \) still handles \( p_1 \) correctly, since \( p_1 \) can either choose \( s_1 \), displacing no one, or \( s_2 \) through \( s_{99} \), displacing someone.)

\( f(1) \) should give the solution to the problem. Embarrassingly, I don't know how to compute the closed form of such a thing. Experimental results (yeah, yeah) suggest that \( f(1) = 2^{100-2} = 2^{98} \), which is the answer we seek. Maybe someone else can show how to get the closed form?

Christopher Johnson - 4 years ago

Log in to reply

Let \(g(n)\) be the number of ways of sitting \(n\) people in the cinema with \(n\) seats, with visitor \(n\) sitting in seat \(n\). Certainly \(g(1) = g(2) = 1\) and \(g(3) = 2\).

Suppose that \(n \ge 4\). Suppose that the first visitor sits in seat \(j\).

  • If \(j=1\), then every visitor sits in their own numbered seat.

  • If \(2 \le j \le n-1\), then visitor \(k\) sits in seat \(k\) for \(2 \le k \le j-1\). What happens to visitors \(j\) to \(n\) is basically the original problem, but for a cinema of size \(n+1-j\), as you noticed.

Thus \[ g(n) \; = \; 1 + \sum_{j=2}^{n-1}g(n+1-j) \; = \; \sum_{j=2}^ng(n+1-j) \; = \; \sum_{j=1}^{n-1}g(j) \qquad \qquad (\star)\] and we note that this identity is in fact true for all \(n\ge 2\).

Consider the generating function \[ G(x) \; = \; \sum_{n=1}^\infty g(n) x^n \] (as we shall see below, this power series has radius of convergence \(\tfrac12\), so all these calculations will be eventually seen to be valid). Now \[ \begin{array}{rcl} (1-x)^{-1}G(x) & = & \left(\sum_{m=0}^\infty x^m\right)\left(\sum_{n=1}^\infty g(n)x^n\right) \; = \; \sum_{N=1}^\infty \left(\sum_{n=1}^N g(n)\right)x^N \\ & = & \sum_{N=1}^\infty g(N+1)x^N \\ x(1-x)^{-1}G(x) & = & \sum_{N=1}^\infty g(N+1)x^{N+1} \; = \; \sum_{N=2}^\infty g(N)x^N \; = \; G(x)-x \\ \frac{1-2x}{1-x}G(x) & = & \big[1 - (1-x)^{-1}\big]G(x) \; = \; x \\ G(x) & = & \frac{x(1-x)}{1-2x} \; = \; (x - x^2)\sum_{n=0}^\infty 2^nx^n \\ & = & x + \sum_{n=2}^\infty 2^{n-2}x^n \end{array}\] so that \(g(n) = 2^{n-2}\) for all \(n \ge 2\).

Of course, if we had guessed the answer that \(g(n) = 2^{n-2}\) for all \(n \ge 2\), then the result could have been proved by induction using \((\star)\). The use of generating functions enabled us to get the answer without knowing it first!

Mark Hennings - 4 years ago

Log in to reply


Jeet Dutta - 3 years, 5 months ago

Log in to reply

much like solving binary problems...

Fahad Shihab - 4 years ago

Log in to reply


Problem Loading...

Note Loading...

Set Loading...