HMMT February, 2018

Solution:

We let $f(n)$ denote the smallest amount we can guarantee to pay at most if Arnold's first choice is $n$. For each $k < n$, if Arnold's first choice is $k+1$, in both worst case scenarios, he could end up paying either $n-k$ or $11+f(k)$. It is then clear that
$$f(n) = \min_{k+1 < n} \max \{ n-k, 11+f(k) \}.$$
Now clearly $f(k)$ is a non-decreasing function of $k$, and $n-k$ is a strictly decreasing function of $k$. Therefore if there exists $k$ such that $n-k = 11+f(k)$, we have $f(n) = n-k = 11+f(k)$ with picking $k+1$ as an optimal play (and picking $K+1$ also optimal iff $K \geq k$ and $f(K) = f(k)$).

Now note that $f(k) = k$ for $k \leq 12$ (but $f(13) = 12$ though it's not relevant to the solution). Let $a_1 = 11$. Now recursively define $a_i$ such that $a_i - a_{i-1} = 11 + f(a_{i-1})$. Thus $f(a_i) = a_i - a_{i-1}$ with the optimal move to pick $a_{i-1} + 1$.

$a_1 = 11$

$a_2 - 11 = 11 + 11: a_2 = 33, f(a_2) = 22$

$a_3 - 33 = 11 + f(33): a_3 = 66, f(a_3) = 33$

It is clear by induction that $a_i$ is 11 times the $i$th triangular number. 1001 is $11 \times 91 = \frac{14 \times 13}{2}$, so the optimal strategy is to pick 1 more than $11 \times \frac{12 \times 13}{2} = 858$. So the answer is 859.