problem 92

(a): Let $S$ be the sum of the ranks of the dishes we eat during both phases. $S = (m - k + 1) X + \sum_{j = 1}^{k - 1} R_{j}$ , where $R_{j}$ is the rank of dish $j$ , excluding the highest ranked dish, from the exploration phase. Since $E (R_{j}) = \frac{(X - 1) X}{2} \times \frac{(\frac{X - 2}{k - 2})}{(k - 1) (\frac{X - 1}{k - 1})} = \frac{(X - 1) X}{2} \times \frac{1}{X - 1} = \frac{X}{2}$ , $E (S) = (m - k + 1) E (X) + (k - 1) \frac{E (X)}{2} = (m - k) E (X) + (k + 1) \frac{E (X)}{2} .$
(b): $P (X = x) = \frac{(\frac{x - 1}{k - 1})}{(\frac{n}{k})} .$
(c): $\begin{matrix} E (X) & = \frac{1}{(\frac{n}{k})} \sum_{i = k}^{n} i (\frac{i - 1}{k - 1}) = \frac{1}{(\frac{n}{k})} \sum_{i = k}^{n} k (\frac{i}{k}) = \frac{k}{(\frac{n}{k})} \sum_{i = k}^{n} (\frac{i}{k}) = \frac{k}{(\frac{n}{k})} (\frac{n + 1}{k + 1}) = \frac{k (n + 1)}{k + 1} \end{matrix}$
(d): Plugging $\frac{k (n + 1)}{k + 1}$ into the result of part $b$ and derivating $(m - k) \frac{k (n + 1)}{k + 1} + k \frac{n + 1}{2}$ with respect to $k$ provides an extremum of $k = \sqrt{2 (m + 1)} - 1$ .