Average Visibility of Moviegoers
Problem
Solution 1
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.
Solution 2
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)}.$
Acknowledgment
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.
|Contact| |Front page| |Contents| |Probability|
Copyright © 1996-2018 Alexander Bogomolny72019476