Average Visibility of Moviegoers

Observe that the $i^{th}$ tallest person is viewable if and only if he is in front of all the people $1,2,\ldots,i-1.$ This happens with probability $\displaystyle \frac{1}{i}.$ Therefore, the answer is

$\displaystyle \sum_{i=1}^{n}\frac{1}{i}\approx \ln n+\gamma, $

where $\gamma=0.5772157\ldots,$ Euler's constant.

For $n$ patrons, let the number of viewable patrons summed over all permutations be $g(n)$. Thus, the average number of patrons over the permutations is $g(n)/n!$ (denote this by $f(n))$.

There are $(n-1)!$ permutations where the tallest person is last in line. For this case, the sum of viewable patrons over all permutations is $g(n-1)+(n-1)!$ ($g(n-1)$ for the first $n-1$ in line and $(n-1)!$ because the tallest patron is a viewable patron for all the permutations).

If a patron other than the tallest patron is last in line, the sum of viewable patrons over all permutations where the last patron is held fixed is $g(n-1)$ (the last patron is not a viewable patron in this case). However, the last patron can be chosen in $(n-1)$ ways for this case. Thus,

$\displaystyle \begin{align} g(n)&=g(n-1)+(n-1)!+(n-1)g(n-1) \\ &=(n-1)!+ng(n-1) \\ \Rightarrow\; f(n)&=\frac{1}{n}+f(n-1)~\text{(Dividing both sides by $n!$)}. \end{align}$

Noting that $f(1)=1$, the solution of this recurrence relation is

$\displaystyle f(n)=\sum_{k=1}^{n} \frac{1}{k}=H_n~\text{($n^{th}$ harmonic number)}.$

This is problem 2 from the 1992 Indiana College Mathematics Competition, see A Friendly Mathematics Competition by Rick Gillman (ed.) Solution 2 is by Amit Itagi.