Taiwan IMO Selection Camp

Call a nonnegative integer representable if it equals the sum of several (possibly 0 or 1) distinct terms of the sequence. We say that two nonnegative integers $b$ and $c$ are equivalent (written as $b \sim c$) if they are either both representable or both non-representable.

One can easily compute (or check by induction) that
$$S_{n-1} := a_0 + a_1 + \dots + a_{n-1} = 2^n + 2^{\lceil n/2 \rceil} + 2^{\lfloor n/2 \rfloor} - 3.$$
In particular, $S_{2k-1} = 2^{2k} + 2^{k+1} - 3$. Note that, if $n \ge 3$, then $2^{\lceil n/2 \rceil} > 3$, so
$$S_{n-1} > 2^n + 2^{\lceil n/2 \rceil} = a_n.$$
Also notice that $S_{n-1} - a_n = 2^{\lceil n/2 \rceil} - 3 < a_n$. The main tool of the solution is the following claim.

Claim 1. If $S_{n-1} - a_n < b < a_n$ for some $n \ge 3$, then $b \sim S_{n-1} - b$.

Proof. If $b$ is representable, then since $b < a_n$, $b$ must be the sum of some subset of $\{a_0, a_1, \dots, a_{n-1}\}$. So $S_{n-1} - b$ is the sum of the complement.
Conversely, notice that $S_{n-1} - a_n < S_{n-1} - b < a_n$, so similarly, if $S_{n-1} - b$ is representable, then so is $b$. $\square$

Proof. Similar to the proof of Claim 1, if $a_n$ can be represented as the sum of two or more distinct terms, then $a_n$ must be the sum of some subset of $\{a_0, a_1, \dots, a_{n-1}\}$. So $S_{n-1} - a_n$ is the sum of the complement. Conversely, since $S_{n-1} - a_n < a_n$, so if representable, $S_{n-1} - a_n$ is represented by a subset of $\{a_0, a_1, \dots, a_{n-1}\}$ and hence $a_n$ is representable by the complement. $\square$

By Claim 2, it suffices to find infinitely many representable and non-representable numbers of the form $2^{t-3}$

Claim 3. For every $t \ge 3$, we have $2^t \sim 2^{4t-6} - 3$ and $2^{4t-6} > 2^t - 3$.

Proof. Since $S_{2t-3} - a_{2t-2} = 2^{t-1} - 3 < 2^t - 3 < a_{2t-2}$, by Claim 1, we have
$$2^t - 3 \sim S_{2t-3} - (2^t - 3) = 2^{2t-2}.$$
And since $S_{4t-7} - a_{4t-6} = 2^{2t-3} - 3 < 2^{2t-2} < a_{4t-6}$, by Claim 1, we have
$$2^{2t-2} \sim S_{4t-7} - 2^{2t-2} = 2^{4t-6} - 3.$$
Therefore, $2^t - 3 \sim 2^{4t-5} - 3$. The inequality follows from $t \ge 3$ $\square$

Since $2^3 - 3 = 5 = a_0 + a_1$ is representable, and easy to check that
$$2^7 - 3 = 125 \sim S_6 - 125 = 24 \sim S_4 - 24 = 17$$
is non-representable. So by Claim 3, there are infinitely many representable and non-representable numbers of the form $2^t - 3$.