, 2018

Solution:
Firstly, note that it is always optimal for you to take the case with the largest amount of money. To prove this rigorously, consider a strategy where you don't - then change the first move where you deviate to taking the maximal case. This can only increase your return.

We calculate the probability $f(n, k)$ that, if there are $n$ cases numbered $1, \cdots, n$ in increasing order of value, that you will take case $k$ in the course of play. We claim that $f(n, k) = \frac{k-1}{n-1}$ and prove this by induction on $n/2$ ($n$ always even). The base case $n=2$ is true because you will always take case $2$ and leave case $1$. Then, for the general $n$, you will always take case $n$ (so $f(n, n) = 1$). Afterward, one case at random will be removed. When calculating $f(n, k)$ there is a $\frac{n-1-k}{n-1}$ probability a case numbered greater than $k$ is removed, which inductively gives a probability $f(n-2, k)$. Also, there is a $\frac{k-1}{n-1}$ probability a case numbered less than $k$ is removed, which inductively gives a probability $f(n-2, k-1)$. We can compute
$$\begin{aligned} f(n, k) & = \frac{n-1-k}{n-1} f(n-2, k) + \frac{k-1}{n-1} f(n-2, k-1) \\ & = \frac{n-1-k}{n-1} \cdot \frac{k-1}{n-3} + \frac{k-1}{n-1} \frac{k-2}{n-3} \\ & = \frac{k-1}{(n-1)(n-3)}(n-1-k+k-2) \\ & = \frac{k-1}{n-1} \end{aligned}$$
as desired.

Finally, we must find $\sum_{i=1}^{16} f(16, i) 2^{i-1}$. Using standard procedures, we get
$$\begin{aligned} \sum_{i=1}^{16} f(16, i) 2^{i-1} & = \sum_{i=1}^{15} \frac{i}{15} 2^{i} \\ & = \sum_{i=1}^{15} \frac{i}{15}\left(2^{17}-2^{i+1}\right) \\ & = \frac{1}{15}(15)\left(2^{17}\right)-\frac{1}{15}\left(\sum_{i=1}^{15} 2^{i+1}\right) \\ & = 2^{17} - \frac{1}{15}\left(2^{17}-4\right) \\ & = \frac{14 \cdot 2^{17} + 4}{15} \end{aligned}$$