Solution:

a) Notice that for odd integers $n>2$, the tuple $(1,1, \ldots, 1)$ is expensive. We will prove that there are no expensive $n$-tuples for even $n$.

Lemma 0.1. If an expensive $n$-tuple exists for some $n \geq 4$, then also an expensive $n-2$-tuple.

Proof. In what follows all indices are considered modulo $n$. Let $(a_{1}, a_{2}, \ldots, a_{n})$ be an expensive $n$-tuple and $a_{t}$ the largest element of the tuple. We have the inequalities
$$\begin{aligned} a_{t-1}+a_{t} & \leq 2 a_{t}<2(a_{t}+a_{t+1}) \\ a_{t}+a_{t+1} & \leq 2 a_{t}<2(a_{t-1}+a_{t}) . \end{aligned}$$
Since both $a_{t-1}+a_{t}$ and $a_{t}+a_{t+1}$ are powers of 2 (they are divisors of a power of 2), we deduce from (1) and (2)
$$a_{t-1}+a_{t}=a_{t}+a_{t+1}=2^{r}$$
for some positive integer $r$, and in particular $a_{t-1}=a_{t+1}$.

Consider now the $n-2$-tuple $(b_{1}, \ldots, b_{n-2})$ obtained by removing $a_{t}$ and $a_{t+1}$ from $(a_{1}, a_{2}, \ldots, a_{n})$. By what we just said we have
$$\prod_{i=1}^{n-2}(b_{i}+b_{i+1})=\frac{\prod_{i=1}^{n}(a_{i}+a_{i+1})}{(a_{t-1}+a_{t})(a_{t}+a_{t+1})}=2^{2(k-r)-1}$$
and hence $(b_{1}, \ldots, b_{n-2})$ is again expensive.

From the lemma we now conclude that if there exists an expensive $n$-tuple for some even $n$, then also an expensive 2-tuple, i.e.
$$(a_{1}+a_{2})^{2}=2^{2k-1}$$
for some positive integers $a_{1}, a_{2}$, which is impossible since the right hand side is not a square.

b) We prove this by induction. In a) we saw that 1 belongs to an expensive $n$-tuple. Assume now that all odd positive integers less than $2^{k}$ belong to an expensive $n$-tuple, for some $k \geq 1$. Hence for any odd $r<2^{k}$ there is an integer $n$ and an expensive $n$-tuple $(a_{1}, \ldots, r, \ldots, a_{n})$. We notice that then also $(a_{1}, \ldots, r, 2^{k+1}-r, r, \ldots, a_{n})$ is expensive. Since $2^{k+1}-r$ can take all odd values between $2^{k}$ and $2^{k+1}$ the induction step is complete.

Solution:

a) For odd $n$ the tuple $(1,1, \ldots, 1)$ is a solution.

Now consider $n$ even. Since the product $\prod(a_{i}+a_{i+1})$ is a power of two, every factor needs to be a power of two. We are going to prove that for all tuples $(a_{1}, \ldots, a_{n})$ such that $a_{i}+a_{i+1}$ is always a power of two, it is the case that $\prod(a_{i}+a_{i+1})$ is equal to an even power of two. We are going to prove this with strong induction on $\sum a_{i}$.

When all $a_{i}$ are equal to one this is certainly the case. Since $a_{i}+a_{i+1}>1$ it is even and we conclude that the $a_{i}$ are either all odd or all even. In the case they are all even, then consider the tuple $(b_{1}, \ldots, b_{n})$ with $b_{i}=a_{i} / 2$. This tuple clearly satisfies the hypothesis as well and we have $\sum b_{i}<\sum a_{i}$. Furthermore we have $\prod(a_{i}+a_{i+1})=2^{n} \prod(b_{i}+b_{i+1})$ and since $n$ is even we are done in this case.

Now all $a_{i}$ are odd. Suppose none of them are one, then consider the tuple $(b_{1}, \ldots, b_{n})$ with $b_{i}=(a_{i}+(-1)^{i}) / 2$. Since all $a_{i}$ are odd and strictly larger than one, the $b_{i}$ are positive integers and satisfy $b_{i}+b_{i+1}=(a_{i}+a_{i+1}) / 2$, a power of two. Since $\sum b_{i}<\sum a_{i}$ and $\prod(a_{i}+a_{i+1})=2^{n} \prod(b_{i}+b_{i+1})$ we are done in this case again.

Now there is at least one $a_{i}$ being one. We may assume $i=1$, because the condition is cyclic. Moreover we may also assume that $a_{2}>1$ since not all of the $a_{i}$ are equal to one. Let now $k$ be the smallest index larger than one such that $a_{k}$ is equal to one. We are not excluding the case $k=n+1$, yet. Now for $i=1, \ldots, k-1$ we have $a_{i}+a_{i+1}>2$ and thus divisible by four. By induction it easily follows that $a_{i} \equiv(-1)^{i+1} \bmod 4$ for $i=1, \ldots, k-1$. In particular, since $a_{k}=1$ we find that $k$ is odd and at least three.

Now consider the tuple $(b_{1}, \ldots, b_{n})$ with $b_{i}=(a_{i}-(-1)^{i}) / 2$ for $i=1, \ldots, k$ and $b_{i}=a_{i}$ otherwise. This is again a tuple that satisfies the hypothesis, since $b_{1}=a_{1}=1=b_{k}=a_{k}$. Moreover $b_{2}<a_{2}$ and thus $\sum b_{i}<\sum a_{i}$. Finally we have $\prod(a_{i}+a_{i+1})=2^{k-1} \prod(b_{i}+b_{i+1})$ and since $k$ is odd we conclude the proof.

b) We use some of the ideas from a). Consider the operators $T_{\pm}(n)=2n\pm 1$. We claim that for every odd integer $m$ there is an integer $r$ and signs $\epsilon_{i} \in\{+,-\}$ for $i=1, \ldots, r$ such that $T_{\epsilon_{r}} \circ \ldots \circ T_{\epsilon_{1}}(1)=m$. This is certainly true for $m=1$ and for $m>1$ we find that $m=T_{-}((m+1)/2)$ if $m \equiv 1 \bmod 4$ and $m=T_{+}((m-1)/2)$ if $m \equiv 3 \bmod 4$. Note that both $(m+1)/2$ and $(m-1)/2$ are odd integers in their respective cases and $(m-1)/2 \leq (m+1)/2 < m$ for $m>1$. Therefore iterating the procedure will eventually terminate in one.

For the construction it is most convenient to set $n=2l+1$ and label the tuple $(a_{-l}, a_{-l+1}, \ldots, a_{l})$. For $m=1$ we have the expensive tuple $(1,1,1)$. For $m>1$ we will define operators $T_{\pm}$ on expensive tuples with the condition $a_{-l}=a_{l}=1$ that give rise to a new expensive tuple $(b_{-l'}, \ldots, b_{l'})$ with $b_{-l'}=b_{l'}=1$ and $b_{0}=T_{\pm} a_{0}$. It is then clear that $T_{\epsilon_{r}} \circ \cdots \circ T_{\epsilon_{1}}((1,1,1))$ is an expensive tuple containing $m$.

We define $T_{\pm}$ as follows: set $l'=l+1$ and $b_{-l'}=b_{l'}=1$ and $b_{i}=T_{\pm(-1)^{i}}(a_{i})$ for $i=-l, \ldots, l$. Here we identify $+$ with $+1$ and $-$ with $-1$. We are left to prove that the new tuple is indeed expensive. If $\pm(-1)^{l}=-1$, then $\prod(b_{i}+b_{i+1})=4 \cdot 2^{2l} \prod(a_{i}+a_{i+1})$, and if $\pm(-1)^{l}=+1$, then $\prod(b_{i}+b_{i+1})=4 \cdot 2^{2l+2} \prod(a_{i}+a_{i+1})$. In both cases we end up with an expensive tuple again.