I think the answer is all $n$ odd numbers. Easily can be shown that odd numbers satisfy. Now I am trying to show evens dont satisfy.

Murad.Aghazade wrote: I think the answer is $n=2$ and all $n$ odd numbers. Easily can be shown that odd numbers satisfy. Now I am trying to show evens dont satisfy. How is $n=2$ a solution? $(a_1+a_2)(a_2+a_1)$ is always a perfect square...

Fixed thanks. Does anyone think also that even dont work here?

This problem is proposed by Harun Hindija (Bosnia and Herzegovina)

a) First, if $n$ is odd just choose $a_1=a_2=\cdots=a_n=1$. Suppose that it's possible when $n$ is even. The $a_i$s must all have the same parity, and if they are all even we can divide all of them by $2$ (their product is divided by an even-th power of $2$ so the condition is still maintained), so WLOG they are all odd. Now for each $n\in\mathbb{N}$, let $s(n)$ be the sum of digits in the binary representation of $n$. Observe that if $x,y$ are odd numbers s.t. $x+y=2^z$ then $s(x)+s(y)=z+1$. Let $a_i+a_{i+1}=2^{b_i}$ for each $i$ where indices are taken $\mod n$. We have $$0\equiv(s(a_1)+s(a_2))+(s(a_2)+s(a_3))+\cdots+(s(a_n)+s(a_1)) \equiv b_1+b_2+\cdots+b_n + n \equiv 2k-1+n\equiv 1\pmod{2}$$which is a contradiction b) For each odd integer $k>1$, define $f(k)$ in two steps: - First, let $b$ be the integer such that $2^{b-1} < k<2^b$. - Then, define $f(k)=2^b-k$. It follows that $f(k)$ is odd and $f(k)<2^{b-1}<k$. Also define $f(1)=1$. Now consider the sequence $m,f(m),f(f(m)),\cdots$ which must be strictly decreasing until we encounter a $1$; and so this sequence must eventually contain a $1$. Let $t$ be the minimal number s.t. $f^t(m)=1$. Then, choose $a_1=m, a_2=f(m), \cdots, a_{t+1}=f^t(m)=1, a_{t+2}=1, a_{t+3}=f^{t-1}(m),\cdots, a_{2t+1}=f(m)$, so $$\prod_{i=1}^n (a_i+a_{i+1}) = (m+f(m))^2(f(m)+f(f(m))^2\cdots(f^{t-1}(m)+f^t(m))^2 2$$Since $m+f(m),f(m)+f(f(m)),\cdots$ are all powers of $2$, it follows that $(m+f(m))(f(m)+f(f(m))\cdots(f^{t-1}(m)+f^t(m))=2^u$ for some $u$, and thus the above product is $2^{2u+1}$ as required.

a) Setting $a_1 = a_2 = \dots = a_n = 1$ gives that all odd numbers satisfy. For $n = 2m$ we show by induction on $m$ that no $2m$-tuple is expensive. For $m = 1$ this is clear. Now assume there exists an expensive $2m$-tuple and consider two consecutive elements $a_i, a_{i + 1}$ with maximal sum ($a_{n + 1} = a_1$). Then $a_{i - 1} + a_i > a_i$ and $a_{i + 1} + a_{i + 2} > a_{i + 1}$ so $\max(a_{i - 1} + a_i, a_{i + 1} + a_{i + 2}) > \max(a_i, a_{i + 1}) \geq \frac{a_i + a_{i + 1}}{2}$ which implies one of the sums $a_{i - 1} + a_i, a_{i + 1} + a_{i + 2}$ is equal to $a_i + a_{i + 1}$ as all sums are powers of 2. Wlog $a_{i - 1} + a_i = a_i + a_{i + 1}$, so $a_{i - 1} = a_{i + 1}$. We claim that $(a_1, a_2, \dots, a_{i - 1}, a_{i + 2}, a_{i + 3}, \dots, a_n)$ is an expensive $(n - 2)$-tuple. This holds because $a_{i - 1} + a_{i + 2} = a_{i + 1} + a_{i + 2}$, so the product of the sums of consecutive pairs is equal to $$\frac{(a_1 + a_2)(a_2 + a_3)\dots(a_n + a_1)}{(a_{i - 1} + a_i)(a_i + a_{i + 1})}$$ Which is a power of 2 to an odd power because the numerator is and $a_{i - 1} + a_i, a_i + a_{i + 1}$ are equal powers of 2. This contradicts the induction hypothesis. b) Let $f(r)$ be the minimal positive integer $k$ such that $r + k$ is a power of $2$. Notice $f(m)$ is odd for $m$ odd and $0 <f(m) < m$ for $m > 1$ odd. Let $k$ be minimal such that $f^k(m) = 1$, we claim that $f^k(m), f^{k-1}(m), \dots, f(m), m, f(m), \dots, f^{k - 1}(m), f^k(m)$ is an expensive $(2k + 1)$-tuple. By definition $f^{t}(m) + f^{t + 1}(m)$ is a power of $2$, and this power appears twice for $t = 0, 1, \dots, k - 1$. The only other term is $f^k(m) + f^k(m) = 2$ and thus the product of consecutive pairs is indeed a power of $2$ with an odd exponent.

A truly excellent problem! Two comments: 1. Since part (b) is easier than part (a), the problem committee should have switched the two parts. 2. Part (a) really seems to need positive integers $a_1,\ldots,a_n$ to go through. Note that the (illegal) six-tuple $(0,2,2,0,4,4)$ yields a product of $2\cdot4\cdot2\cdot4\cdot8\cdot4=2^{11}$.

Here is my approach for $n$ even in part a). Clearly $n=2$ is not possible. So assume $n\geq 4$ and $n$ is minimal. WLOG $a_n=\max a_i$. Since $a_{n-1}\leq a_n$ and $a_{n-1}+a_n$ is a power of $2$, $a_{n-1}$ is unique. Similarly $a_1$ is unique. Hence $a_{n-1}=a_1$. So $(a_2,a_3\dots,a_{n-1})$ is a smaller counterexample, contradiction.

Wrong

(a) The answer is $n$ odd, with the construction $a_1=a_2=\ldots=a_n=1$. We show that for $n$ even we have that $\prod(a_i+a_{i+1})$ is always a perfect square by induction, with the base case of $n=2$ leading to $(a_1+a_2)^2$. For the inductive step, note that $a_i+a_{i+1}$ are all powers of 2. Take the maximal power of 2 among them, call it $2^N=a_k+a_{k+1}$, and WLOG suppose that $a_k\ge a_{k+1}$, so $a_k\ge2^{N-1}$. Then, $2^{N-1}<a_{k-1}+a_k\le 2^N$, so we must have that $a_{k-1}+a_k=2^N=a_k+a_{k+1}\implies a_{k-1}=a_{k+1}$. Replacing $a_{k-1},a_k,a_{k+1}$ with $a_{k-1}$ decreases $n$ by 2 and divides $\prod(a_i+a_{i+1})$ by $2^{2N}$. By the inductive hypothesis, $\prod(a_i+a_{i+1})$ is a perfect square, as desired. (b) For an odd positive integer $m$, let $f(m)=2^k-m$, where $2^k$ is the smallest power of 2 greater than $m$. Note that $f(m)<m$ unless $m=1$ in which case $f(1)=1$, so the sequence $m,f(m),f(f(m)),\ldots$ eventually hits 1. Let $(b_1,b_2,\ldots,b_i)=(m,f(m),\ldots,1)$, and set $(a_1,a_2,\ldots,a_{2i-1})=(b_1,b_2,\ldots,b_i,b_i,b_{i-1},\ldots,b_2$. This gives twice a perfect square of a power of two, as desired.

(a) We claim that there expensive $n$-tuples if and only if $n$ is odd. If $n$ is odd, simply take $a_1 = a_2 = \ldots = a_n = 1$. For even $n$, we use infinite descent. Consider an expensive $n$-tuple $(a_1, \ldots, a_n)$ with $n$ even and minimal, so \[P := \prod_{i=1}^n (a_i+a_{i+1}) = 2^{2k-1}\]for some $k$. (Here we set $a_{n+1} = a_1$.) If $n=2$, then $P = (a_1+a_2)^2 = 2^{2k-1}$, impossible since the right-hand side is not a perfect square. Thus $n \ge 4$. Each of the $n$ factors $(a_i+a_{i+1})$ must be a power of $2$, so let $a_i + a_{i+1} = 2^{e_i}$ for each $1 \le i \le n$. WLOG, let $e_1 = \text{max}(e_1, \ldots, e_n)$. Note \[2^{e_n} + 2^{e_2} = (a_n + a_1) + (a_2 + a_3) > (a_1 + a_2) = 2^{e_1}\]but by assumption we have $e_n \le e_1$ and $e_2 \le e_1$. This forces either $e_n = e_1$ or $e_2 = e_1$. WLOG, let $e_2 = e_1$. Then $a_2 + a_3 = a_1 + a_2$, so $a_1 = a_3$. Then \[P = (a_1+a_2)(a_2+a_3)\prod_{i=3}^n (a_i+a_{i+1}) = 2^{2e_1} (a_3+a_4)\ldots(a_n+a_1)\]but $a_1 = a_3$, so $(a_3, a_4, \ldots, a_n)$ must also be expensive. This contradicts the minimality assumption and completes the proof.

I ignored it at the time that EGMO came out, but part (a) is actually quite nice. The idea is quite similar to Taiwan TST Quiz 2014/3J/5 which is one of my all-time favorite problems. For part (a), the answer is odd $n$, with construction given by setting $a_1 = \dots = a_n = 1$. We show by induction that even $n$ all fail, with $n=2$ being plain. Construct a regular $n$-gon whose vertices are labeled $a_i$ and edges are labeled with $a_i + a_j$. [asy][asy] size(4cm); int[] x = {7,1,15,1,3,1,7}; for (int i=0; i<6; ++i) { dot( (string) x[i], dir(60*i), dir(60*i), darkcyan); draw(dir(60*i)--dir(60*i+60), darkcyan); label( (string) (x[i] + x[i+1]), midpoint(dir(60*i)--dir(60*i+60)), dir(60*i+30), red); } [/asy][/asy] Then we observe that it's impossible for an edge to exceed both of its neighbors, since if $a+b = 2^e$ then $\min(a+1, b+1) > 2^{e-1}$. Consequently we can take two adjacent edges $a+b = b+c$ with the same label; hence $a = c$. Then delete $b$, $c$ and induct down. For part (b), for odd integers $m$, let $f(m)$ denote $2^k - m$ where $2^k$ is the smallest power of two exceeding $m$. Note $f(m) \le m$ with equality if and only if $m = 1$. So repeatedly apply $f$ until we wrap around; this gives twice a square of a power of two. Example when $m = 13$: [asy][asy] size(4cm); int[] x = {13,3,1,1,3,13}; for (int i=0; i<5; ++i) { dot( (string) x[i], dir(72*i), dir(72*i), darkcyan); draw(dir(72*i)--dir(72*i+72), darkcyan); label( (string) (x[i] + x[i+1]), midpoint(dir(72*i)--dir(72*i+72)), dir(72*i+30), red); } [/asy][/asy]

Wow, I used the same notation as Evan :p (by chance) (a) We claim only $n$ odd works. If $n$ is odd, simply let $a_i=1$ for all $i$. Now, we show that $n$ even doesn't work. First, we note that $n=2$ fails because the left side is a perfect square. Now, suppose $(a_1,\ldots,a_n)$ works where $n$ even. Suppose WLOG $a_2\ge a_i$ for all $i$. Then, we see that $a_1=a_3=2^e-a_2$ where $2^e$ is the smallest power of $2$ greater than $a_2$. Thus, $(a_3,\ldots,a_n)$ is a valid configuration, so we conclude by induction on $n$. (b) Let $f(x)=2^e-x$ where $2^e$ is the smallest power of $2$ greater than $x$. Note that $m$ odd implies that $f(m),f(f(m)),\ldots$ eventually stops at $1$. Then, we see that $(f^r(m),f^{r-1}(m),\ldots,f(m),m,f(m),\ldots,f^{r-1}(m),f^r(m))$ works where $f^r(m)=1$.

Nice problem. Here's my solution (hope it's correct ): Note that $a_i+a_{i+1}$ has only $2$ as its prime factor $\forall i \in \{1,2, \dots ,n-1\}$, which means that all $a_i$'s have same parity. Part a) We claim that there exists an expensive $n$-tuple iff $n$ is odd. The if part is obvious if one takes $a_1=a_2= \dots =a_n=1$. For the only if part, we assume, to the contrary, that some even $n$ works. Take $n=2m$. If all $a_i$'s are even, then we can repeatedly divide the given equality by $2^n$ and keep getting expensive $n$-tuples till all the new $a_i$'s become odd. So we can assume that all $a_i$'s are odd. Then we can take $a_i=2b_i-1 \text{ } \forall i \in \{1,2,\dots ,n\}$, where $b_i \geq 1$. Substituting this in the given equality, and dividing by $2^n$, we have $$(b_1+b_2-1)(b_2+b_3-1) \dots (b_{n-1}+b_n-1)(b_n+b_1-1)=2^{2(k-m)-1}$$which gives that $k$ must be greater than $m$ (as the LHS is an integer). Now, Consider the $n$-tuple $(b_1,b_2-1,b_3,b_4-1,\dots,b_{n-1},b_n-1)$. Then by a similar argument as we performed on the expensive $n$-tuple $(a_1,a_2,\dots,a_n)$, one can easily get that all entries of this $n$-tuple must also be odd, which in turn gives that $b_i$ and $i$ have the same parity. As $b_i \geq 1 \text{ } \forall i \in \{1,2, \dots,n \}$, we get that $b_{2r} \geq 2$, since $b_{2r}$ is even. This means that all entries of this $n$-tuple are positive. But then, using the above equality, we have that the $n$-tuple $(b_1,b_2-1,b_3,b_4-1,\dots,b_{n-1},b_n-1)$ is also expensive. Again take $b_{2r-1}=2c_{2r-1}-1$ and $b_{2r}=2c_{2r}$, and apply the same whole process once more. If we keep repeating this process, then we get that $k$ must be greater than $pm \text{ } \forall p \in \mathbb{N}$, which is not possible if $k$ is finite. ($k$ is a part of the original equation and $m=\frac{n}{2}$, in case you forgot ). Thus, we get that if $n$ is even,then no expensive $n$-tuple exists, hence proving our claim. $\blacksquare$ Part b) My solution to this part is quite similar to the above solutions (and I think it is actually quite intuitive, one of the main reasons why there are so few different solutions to this part), but still I'll post it for the sake of completeness. Note that $m=1$ works (follows from first line in the proof of Part a)). So from now on assume that $m>1$. Let $M$ be the smallest power of $2$ which is greater than $m$, where $m$ is an odd positive integer, i.e. $2^{M-1}<m<2^M$. Define a function $f:2\mathbb{Z}+1 \rightarrow 2\mathbb{Z}+1$, such that $f(m)=2^M-m$. Now, as $m>2^{M-1}$, we must have $f(m)<m$, which in turn gives that the sequence $\{m,f(m),f(f(m)), \dots \}$ is a strictly decreasing sequence over the set of odd positive integers, and so it must finally become equal to one at some stage, after which it will always remain one (as we have $f(1)=1$). Suppose that $s$ is the smallest positive integer such that $f^s(m)=1$, where $f^s(m)$ denotes the function $f$ applied $s$ times to $m$. Then consider the $(2s+1)$-tuple $\{f^s(m),f^{s-1}(m),\dots,f(m),m,f(m),\dots,f^{s-1}(m),f^s(m) \}$. By the definition of $f$, and using the fact that $f^s(m)=1$, one can easily see that this $(2s+1)$-tuple is expensive, thus proving that $m$ is a part of some expensive tuple for all odd positive integers $m$. $\blacksquare$

tenplusten wrote: I think the answer is all $n$ odd numbers. Easily can be shown that odd numbers satisfy. Now I am trying to show evens dont satisfy. nono it said {ai} are positve integers . so there can't be 0...

Remark: Good one! Quite the nice problem. Also how's remark before solution a) We claim that the answer is all odd $n$. These clearly work by letting all $a_i = 1$. It suffices to show that evens fail. Notice that when $n = 2$ then the LHS is a perfect square hence bad. Now consider $n \geq 4$. We will finish by contradiction. Suppose that some $2k$-tuple $(a_1, a_2, \ldots , a_{2k})$ works. WLOG suppose $a_1$ is the largest term. Then, since the LHS product is a power of $2$, so must each term be, hence $a_1 + a_2$ and $a_1 + a_{2k}$ are all powers of $2$. Note that $a_1$ and $a_{2k}$ must be equal, both to $2^m - a_1$ where $m$ is the smallest power of $2$ greater than $a_1$. Else, $a_2, a_{2k} > a_1$. Therefore, we have reduced the result to $(a_2, a_3, \ldots , a_{2k-1})$, so keep inducting down (deleting $2$ terms each time) to eventually reach $n = 2$ and get a contradiction. $\blacksquare$ b) Let $a$ be an odd integer. Then, $f(a) = 2^b - a$ where $2^b$ is the least power of $2$ greater than $b$. Clearly $f(a) \leq m$ for all $a$. If not, we can choose a smaller power of $2$. Furthermore, equality occurs if and only if $a = 1$. Hence, the chain $f(a), f(f(a)), \ldots$ eventually reaches $1$ and stays constant. Lastly, if we let $c$ be the smallest positive integer for which $f^c(a) = 1$, then the tuple\[(f^c(a), f^{c-1}(a), \ldots , f(a), a, f(a), f^2(a), \ldots f^c(a))\]conveniently produces a power of two value and is hence expensive, as desired. $\blacksquare$

(a) We claim that there exists an expensive $n$-tuple if and only if $n$ is odd. It is easy to see that $(1,1,\dots,1)$ is an expensive $n$-tuple when $n$ is odd, so it remains to show that there are no expensive $n$-tuples for even $n.$ Induct on $n,$ the base case being clear. Assume the claim is true for $n-2,$ and consider an $n$-tuple $(a_1,a_2,\dots,a_n)$ such that $n$ is even and $a_i+a_{i+1}=2^{t_i}$ is a power of two for $i\in\{1,2,\dots,n-1\}.$ Note that $$(a_1+a_2)(a_2+a_3)\dots (a_n+a_1)=2^{t_1+t_2+\dots+t_{n-1}}(2^{t_{n-1}}-2^{t_{n-2}}+2^{t_{n-3}}-\dots+2^{t_1}). $$WLOG assume $\min(t_{n-1},t_{n-3},\dots,t_{1})=t_1$ and $\min(t_{n-2},t_{n-4},\dots,t_{2})=t_2.$ We have two cases: $\textbf{Case 1: }$ $t_1<t_2$ (WLOG) Then, we must have $$2^{t_{n-1}}-2^{t_{n-2}}+2^{t_{n-3}}-\dots+2^{t_1}=2^{t_{1}}$$$$\implies 2^{t_{n-1}}-2^{t_{n-2}}+2^{t_{n-3}}-\dots+2^{t_3}=2^{t_2}. $$Therefore, by the inductive hypothesis, $t_2+t_3+\dots+t_{n-1}$ is even, so let $t_2+t_3+\dots+t_{n-1}=2k$ for some $k.$ Then, $$2^{t_1+t_2+\dots+t_{n-1}}(2^{t_{n-1}}-2^{t_{n-2}}+2^{t_{n-3}}-\dots+2^{t_1})=2^{t_1+2k}2^{t_1}=2^{2k+2t_1},$$which is not twice a power of four, as desired. $\textbf{Case 2: }$ $t_1=t_2$ Since $t_1+t_2$ is even, we are done by the inductive hypothesis. (b) Let $f(x)$ be the smallest power of two greater than $x.$ Define the sequence $\{x_i\}$ by the recursion $$x_{1}=m,$$$$x_{i+1}=f(x_i)-x_i.$$Let $x_k$ be the first term of this sequence equal to $1.$ We have $$(x_1+x_2)(x_2+x_3)\dots (x_{k-1}+x_k)(x_k+x_k)(x_{k}+x_{k-1})\dots (x_3+x_2)(x_2+x_1)$$$$=2[(x_1+x_2)(x_2+x_3)\dots (x_{k-1}+x_{k})]^2.$$Since $x_i+x_{i+1}$ is a power of $2$ for $i\in\{1,2,\dots,k-1\},$ this expression is twice a power of four. Hence, the $2k-1$-tuple $$(x_1,x_2,\dots,x_k,x_k,x_{k-1},\dots,x_1)$$is expensive, as desired.

(a) The answer is $n$ odd. For $n$ odd, simply take all 1's. Now we show no expensive tuple exists for $n$ even. Induct on $n$, $n=2$ easy. Suppose an expensive $n$-tuple existed. Let $a_i+a_{i+1}=2^{k_i}$ for $i=1,\ldots,n$ (let $a_{n+1}=a_1$). Consider a maximal $k_i$, call it $M$. Consider the longest chain of these maximal pair-sums. We claim this chain has length at most 1. Suppose it has length at least 2, then $a_{i}+a_{i+1}=2^{M}$ and $a_{i+1}+a_{i+2}=2^M$, so $a_i=a_{i+2}$. This means we can remove $a_i$ and $a_{i+1}$ from the tuple, and the remaining tuple is also expensive, since we divided out by $2^{2M}$, a perfect square. But by induction, we cannot have an expensive $(n-2)$-tuple, contradiction. Therefore, $a_i+a_{i+1}=2^M$, and $a_{i-1}+a_{i} \le 2^{M-1}$ as well as $a_i+a_{i+1} \le 2^{M-1}$. But the first statement tells us that one of $a_i,a_{i+1}$ is at least $2^{M-1}$, contradiction. This proves that no expensive $n$-tuples exist for $n$ even. (b) Induct on odd $m$, base case $m=1$ belonging to $(1,1,1)$. Let $2^k$ be the smallest power of 2 more than $m$. So $2^{k-1} < m < 2^k$ (no equality since $m$ odd). Then $2^k-m < m$, so we can construct an expensive $n$-tuple starting with $2^k-m$ by induction. Note that this tuple must end with $m$, since each pair-sum is a power of 2. Then simply tack on $m$ to the beginning (call it $a_0$) and $2^k-m$ to the end (call it $a_{n+1}$). This works since $a_n+a_1$ in the old is now $a_n+a_{n+1}$, and we multiplied on $a_{n+1}+a_{0}=2^k$ and $a_0+a_1=2^k$, for a total of $2^{2k}$, keeping the tuple expensive.

EGMO 2017 P5 wrote: Let $n\geq2$ be an integer. An $n$-tuple $(a_1,a_2,\dots,a_n)$ of not necessarily different positive integers is expensive if there exists a positive integer $k$ such that $$(a_1+a_2)(a_2+a_3)\dots(a_{n-1}+a_n)(a_n+a_1)=2^{2k-1}.$$a) Find all integers $n\geq2$ for which there exists an expensive $n$-tuple. b) Prove that for every odd positive integer $m$ there exists an integer $n\geq2$ such that $m$ belongs to an expensive $n$-tuple. There are exactly $n$ factors in the product on the left-hand side. Solution. Part (a): If we let $a_1=a_2=\cdots =a_n=1\implies n$ odd works, now we need to prove that $n$ even fails, for the case where $n=2$ it clearly doesn't work. Claim: For $n\geq 4$ if there exist an expensive $n$-tuple, then there also exist an expensive $n-2$-tuple. Proof. Let $(a_1, a_2,\cdots ,a_n)$ be an expensive $n$-tuple, and let $a_x$ be the largest element of that tuple. Now we have that: $$a_{x-1}+a_{x}\leq 2a_{x}<2(a_{x}+a_{x+1})$$$$a_x+a_{x+1}\leq 2a_{x}<2(a_{x-1}+a_{x})$$Using this two inequalities and the fact that $a_{x-1}+a_{x}$, $a_{x}+a_{x+1}$ are powers of $2$ we have that $a_{x-1}+a_{x}=a_{x}+a_{x+1}=2^{k}$, and we also have that $a_{x+1}=a_{x-1}$. Now if we create a new $n-2$-tuple by removing $a_{x+1}$, and $a_{x-1}$ we can easily note that the $n-2$-tuple we created is also expensive.$\square$ Now since $n=2$ is not expensive, there doesn't exist an $n$-tuple which is expensive for any $n$ even.$\blacksquare$ Part (b): For $m=1$ is clear that it works. Suppose that all odd positive integers less than $2^k$ works. If $a$ is an odd number and $a<2^k$ there exist a $n$-tuple $(a_1, \cdots , a, \cdots, a_n)$ which is expensive, but $(a_1, \cdots , a, 2^{k+1}-a \cdots, a_n)$ is also expensive. Since $2^{k+1}-a$ can take all odd values between $2^k$ and $2^{k+1}$.$\blacksquare$

The answer to (a) is all odd $n$, which clearly work by picking all $a_i$ to be the same power of two. Suppose even $n$ worked and now suppose each individual term was $2^{a_1}, 2^{a_2}, \cdots, 2^{a_n}$. Write $a_2 = 2^{a_1} - a_1$, $a_3 = 2^{a_2} - a_2 = 2^{a_2} - 2^{a_1} + a_1$, and so on, until we get $2^{a_1} + 2^{a_3} + \cdots + 2^{a_{n-1}} = 2^{a_2} + 2^{a_4} + \cdots + 2^{a_n}$ now induct on $n$, base case of $n = 2$ being true, if there is a term that is common on both sides, then delete and induct, otherwise there must be a pair on each side, with equal values, combine on both sides and induct. For (b), we'll induct on $m$ on the fact that such an expensive tuples exists and it is also fully symmetric. Let $2^k$ be smallest power of $2$ bigger than $m$ (if $m$ is power of $2$, then pick all $a_i$ to be it), and consider the tuple starting with $(m + (2^k - m))$ and ending with $((2^k - m) + m)$ and insert in between, the tuple for $2^k - m$ by inductive hypothesis, the tuple formed now is also clearly symmetric, so induction works and we're done. $\blacksquare$

a) The answer is odd $n$ only. For odd $n$, the tuple $(1,3,1,3,\dots,1,3,1)$ is expensive. For even $n$, we will show that if $\prod_{i=1}^n (a_i + a_{i+1})$ is a power of $2$, then it is a power of $4$ (where indices are taken mod $n$). Since each factor in the product is even, the $a_i$ all have the same parity. If the $a_i$ are all even, we can divide through by $2$ and repeat this argument until the $a_i$ are all odd. Hence, we can assume WLOG that the $a_i$ are all odd. Construct an infinite graph $G$ whose vertices are the odd natural numbers such that $u\neq v$ are connected by an edge if and only if $u+v$ is a power of $2$. Starting with $a_1$, when going from $a_i$ to $a_{i+1}$, we either travel along an edge of $G$ or stay at $1$. Now, notice that each number other than $1$ is connected to exactly $1$ smaller number in $G$. Hence, as we travel from $a_1$ to $a_{n+1} = a_1$ one index at a time, we can only stay at $1$, walk "up" along edges of G, or retrace our path. In particular, each time we walk up along an edge, we will later walk down along that edge. It follows that we walk along edges of $G$ an even number of times, and these edges contribute a power of $4$ to the product. Since $n$ is even, this also means that we stay at $1$ an even number of times, so the moves where we stay at $1$ also contribute a power of $4$ to the product, as desired. b) For $m = 1$, the tuple $(1,3,1)$ is expensive. For $m > 1$, let $f(m)$ denote the least positive integer $m'$ such that $m + m'$ is a power of $2$. Since $m > 1$, we are guaranteed that $f(m) < m$. Then the tuple $$(m,f(m),\dots,f^k(m),1,1,f^k(m),\dots,f(m))$$ is expensive, where $k$ is the least natural number such that $f^{k+1}(m) = 1$.

Part a). The answer is all odd $n$, which clearly work by $a_1 = a_2 = \cdots = a_n = 1$. Now assume $n$ is even. Let $n=2m$. We induct on $m$. Suppose $(a_1, a_2,\ldots, a_{2t})$ was not expensive for any $t<m$. We will show any tuple $(a_1, a_2, \ldots,a_{2m})$ is not expensive. Suppose otherwise. WLOG $a_1 = \max_{i=1}^{2m} (a_i)$. Then we have $a_2,a_{2m}<a_1$, so $a_2 = a_{2m} = 2^e - m$, where $2^e$ is the smallest power of $2$ greater that $a_1$. We get that $a_1 + a_2 = a^{2m} + a_1 = 2^e$ and $a_{n-1} + a_n = a_{n-1} + a_2$, so \[(a_2 + a_3) (a_3 + a_4) \cdots (a_{2m-2} + a_{2m-1}) (a_{2m-1} + a_2) = 2^{2k - 2e - 1},\]which implies $(a_2, a_3, \ldots, a_{2m-1})$ is expensive, contradiction to the inductive hypothesis. Part b) For $m=1$, obviously $(1,1,1)$ works. Now assume $m>1$. Let $f(m)$ denote the distance between $m$ and the largest power of $2$ exceeding $m$. Since $f(m)<m$ for all $m>1$, we have $f^a(m) = 1$ for some $a$. Notice that the tuple \[(m, f(m), f^2(m), \ldots, f^{a-1}(m), 1,1, f^{a-1}(m), \ldots, f^2(m), f(m))\]is expensive and contains $m$.

Work with indices modulo $n$. For part (a) the answer is $n$ odd, which can be achieved by taking all $1$'s. For $n$ even, suppose that the product is a power of two. I will show that it is a power of four. Consider the maximal value $M$ among $a_1,\ldots,a_n$. If $M$ is a power of two, say $2^m$, then it is clear that $a_1=\cdots=a_n=M$: if $a_1=M$, then $a_2=M$ as well otherwise $M<a_1+a_2<2M$, and so on. Otherwise we can write $M=2^m+a$ for $0<a<2^m$, so then if $a_i=M$ then $a_{i-1}=a_{i+1}=2^{m+1}-M=2^m-a$. But then if we replace every instance of $2^m+a$ with $a$, we can see that we divide the product in question by $2$ raised to some even power, which will not change the parity of its $\nu_2$, so induct down (specifically, we induct on $\max a_i$, with the base case of $\max a_i=1$ being obvious), implying that the product is always a power of two as desired. For part (b), we use a similar idea presented in the proof that $n$ even fail in part (a). For an odd positive integer $m>1$ let $f(m)$ denote the least integer such that $m+f(m)$ is a power of two. Note that $f(m)<m$ and $f(m)$ is odd as well. Thus if $f^k(m)=1$, we take the tuple $$(f^k(m)=1,f^{k-1}(m),f^{k-2}(m),\ldots,f(m),m,f(m),\ldots,f^{k-2}(m),f^{k-1}(m)=1).$$For example, if $m=7$ we would construct the tuple $(1,7,1)$, and for $m=11$ we would construct the tuple $(1,3,5,11,5,3,1)$, both of which can be seen to work. $\blacksquare$

Might have tripped up somewhere, not sure. First note that there clearly exists an expensive $n-$tuple for all odd integers $n\geq 3$ simply by letting $a_1=a_2=\dots = a_n=1$ which gives us that \[(a_1+a_2)(a_2+a_3)\dots(a_{n-1}+a_n)(a_n+a_1)=2^{n}\]which is clearly an odd power of two. Now, we shall that there does not exist an expensive $n-$tuple for any even integer $n\geq 2$. First, it is easy to see that when $n=2$ we have that \[(a_1+a_2)^2=(a_1+a_2)(a_2+a_1)=2^{2k+1}\]clearly the LHS is the square of a positive integer but the RHS isn't which implies that there exists no expensive $2-$tuples. Now, consider an even integer $n$. Let $a_1$ be the smallest element in this tuple (one can cycle the variables around so that this is true since the equation is cyclic). It is clear that $a_1+a+2,\dots,a_{n-1}+a_n,a_n+a_1$ must all be powers of two in order for the required equality to hold. So, we have $a_2 \geq a_1$. Let $a_1+a_2=2^A$. Then, $a_2 \geq 2^{A-1}$. Now, clearly $a_2+a_3>2^{A-1}$ and thus, we must have $a_2+a_3\geq 2^A$. If $a_2+a_3=2^A$, we have $a_1=a_3$ and the required equality rewrites to \[(a_1+a_4)(a_4+a_5)\dots (a_n+a_1)=2^{2(n-A)-1}\]which is simply the $n-2$ case. If $a_2+a_3 > 2^A$ then since $a_2<2^A$, we must have $a_3>2^{A}>a_2$. Thus, $a_2>a_3$. Now, say we have $a_1\leq a_2 <a_3 < \dots <a_k$. Then, let $a_k+a_{k-1}=2^{A_k}$. Then, $a_k >2^{A_k-1}$ and thus clearly $a_k+a_{k+1}>2^{A_k-1}$. If $a_k+a_{k+1}=2^{A_k}$ then, we have that $a_{k+1}=a_{k-1}$ and the given equality rewrites to \begin{align*} 2^{2k-1}&= (a_1+a_2)\dots (a_{k-2}+a_{k-1})(a_{k-1}+a_k)(a_k+a_{k+1})(a_{k+1}+a_{k+2})\dots (a_n+a_1)\\ &= (a_1+a_2)\dots (a_{k-2}+a_{k-1})(a_{k-1}+a_k)(a_k+a_{k-1})(a_{k-1}+a_{k+2})\dots (a_n+a_1) \\ 2^{2(k-A_k)-1} &= (a_1+a_2)\dots (a_{k-2}+a_{k-1})(a_{k-1}+a_{k+2})\dots (a_n+a_1) \end{align*}which is simply the $n-2$ case. Thus,we can always reduce to the $n-2$ case or else we must have $a_1\leq a_2 < a_3 < \dots < a_n$. In this case, note that the sum of the bracketed terms must also be increasing. But then, if $a_1+a_2=2^A$ we must have $a_2+a_3=2^{A+1}$ which means $a_3 \equiv -a_2 \pmod{2^{A+1}}$. Similarly, we obtain $a_{2i}\equiv a_2$ and $a_{2i+1}\equiv -a_2$ for all $i\geq 1$. Now, this means, \[a_n+a_1 \equiv a_1+a_2 \equiv 2^A \pmod{2^{A+1}}\]Thus, we must have $a_1+a_1=2^A$ and in turn $a_n=a_2$ which is a very clear contradiction. Now, by the Principle of Mathematical Induction, we have that if there exists an expensive $n-$tuple for any even integer $n\geq 2$, then there must exist an expensive $2-$tuple which we have already proved is false. Thus, there exists no expensive $n-$tuples for even $n$. Now that we have answered part \textbf{(a)} we will look at part \textbf{(b)}. For this simply consider an odd integer $b_1=k$ and the smallest power of two which is greater than $k$, say $2^M$. Now, let $b_2=2^M-k$ and so on. It is clear that this sequence is strictly decreasing since $k>2^{M-1}$ and also, each new term must be odd and thus, this sequence eventually ends with $1$. Thus, we can consider the $n-$tuple, \[(1,1,b_{m},b_{m-1},\dots,b_2,b_1,b_2,\dots, b_m)\]It is clear now that the required product must be an odd power of 2 since each bracketed term is clearly a power of two by the nature of the construction and each bracketed term besides the first comes in pairs. Thus, there always exists some expensive $n-$tuple containing each odd integer $m\geq 1$ and we are done.

For part (a), the answer is $n$ odd only. For construction, just take $(1, 1, \dots, 1)$. To show all even $i$ cannot work, set $b_i = a_{2i-1} + a_{2i}$ and $c_i = a_{2i} + a_{2i+1}$ for $i = 1, 2, \dots, n/2$. I claim that the set $\{b_i \mid 1 \leq i \leq n/2\}$ and $\{c_i \mid 1 \leq i \leq n/2\}$ are identical, which will force the RHS to be a power of $4$. To do this, just induct down. Pick $a_{2k}$ maximal (we WLOG the index to be even) and notice that $b_k = c_k = 2^{\lceil \log_2 a_{2k} \rceil}$. Furthermore, $a_{2k-1} = a_{2k+1}$ as a result. Then replace $\{a_{2k-1}, a_{2k}, a_{2k+1}\}$ with $\{a_{2k-1}\}$, which removes two identical $b_k$ and $c_k$ from the two sets. This completes the induction. For part (b), set $a_1 = m$ and $a_2 = a_n = 2^{\lceil \log_2 m \rceil} -m$. Correspondingly, at every step, let $a_i = 2^{\lceil a_{i-1} \rceil} - a_{i-1}$ and similar for $a_{n-i}$. The sequences $a_1, a_2, \dots$ and $a_n, a_{n-1}, \dots$ are both strictly decreasing, so there will exist $k$ and $\ell$ such that $a_k = a_\ell = 1$. Now we may set every element between $a_k$ and $a_\ell$ equal to $1$ and adjust suitably to ensure the result is not a power of $4$, as needed.