United States — Team Selection Test

The answer is $d_n = \dfrac{2^{2n+1} + 1}{3}$. We first show that $d_n$ cannot be obtained. For any $p$ let $t(p)$ be the minimum $n$ required to express $p$ in the desired form and call any realization of this minimum a minimal representation. If $p$ is even, any sequence of $b_i$ that can produce $p$ must contain an even number of zeros. If this number is nonzero, then canceling one against another or replacing two with a $b_i = 1$ term would reduce the number of terms in the sum. Thus a minimal representation cannot contain a $b_i = 0$ term, and by dividing each term by two we see that $t(2m) = t(m)$. If $p$ is odd, there must be at least one $b_i = 0$ and removing it gives a sequence that produces either $p-1$ or $p+1$. Hence
$$t(2m-1) = 1 + \min(t(2m-2), t(2m)) = 1 + \min(t(m-1), t(m)).$$
With $d_n$ as defined above and $c_n = \dfrac{2^{2n} - 1}{3}$, we have $d_0 = c_1 = 1$, so $t(d_0) = t(c_1) = 1$ and
$$t(d_n) = 1 + \min(t(d_{n-1}), t(c_n)) \quad \text{and} \quad t(c_n) = 1 + \min(t(d_{n-1}), t(c_{n-1})).$$
Hence, by induction, $t(c_n) = n$ and $t(d_n) = n+1$ and $d_n$ cannot be obtained by a sum with $n$ terms.

Next we show by induction on $n$ that any positive integer less than $d_n$ can be obtained with $n$ terms. By the inductive hypothesis and symmetry about zero, it suffices to show that by adding one summand we can reach every $p$ in the range $d_{n-1} \le p < d_n$ from an integer $q$ in the range $-d_{n-1} < q < d_{n-1}$. Suppose that $c_n + 1 \le p \le d_n - 1$. By using a term $2^{2n-1}$, we see that $t(p) \le 1 + t(|p - 2^{2n-1}|)$. Since $d_n - 1 - 2^{2n-1} = 2^{2n-1} - (c_n + 1) = d_{n-1} - 1$, it follows from the inductive hypothesis that $t(p) \le n$. Now suppose that $d_{n-1} \le p \le c_n$. By using a term $2^{2n-2}$, we see that $t(p) \le 1 + t(|p - 2^{2n-2}|)$. Since $c_n - 2^{2n-2} = 2^{2n-2} - d_{n-1} = c_{n-1} < d_{n-1}$, it again follows that $t(p) \le n$.