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.

#Combinatorics #HelpMe! #MathProblem #Math

Easy Math Editor

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.
Stay on topic — we're all here to learn more about math and science, not to hear about your favorite get-rich-quick scheme or current world events.

Markdown	Appears as
`italics` or `_italics_`	italics
`bold` or `__bold__`	bold
- bulleted - list	bulleted list
1. numbered 2. list	numbered list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1 paragraph 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"

Math	Appears 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}$

Comments

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:

Sit in their respective seat $s_i$ , if available.
If they can't do #1, this means that $s_1$ must be available. They can sit there and displace no one else.
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 - 7 years, 8 months ago

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 - 7 years, 8 months ago

much like solving binary problems...

Fahad Shihab - 7 years, 8 months ago

9.33e155

Jeet Dutta - 7 years, 1 month ago

Math	Appears 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}$