Problem: An $n$-tuple $(a_1,a_2,\dots,a_n)$ of positive integers is \emph{expensive} if
\[ (a_1+a_2)(a_2+a_3)\dots(a_{n-1}+a_n)(a_n+a_1) = 2^{2k-1} \]
for some positive integer $k$.
\begin{enumerate}
  \ii[(a)] Find all integers $n \ge 2$ for which there exists an expensive $n$-tuple.
  \ii[(b)] Prove that each odd integer $m \ge 1$
  appears in an expensive $n$-tuple for some $n \ge 2$.
\end{enumerate}

Solution: 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$.
\begin{center}
\begin{asy}
  size(5cm);
  int[] x = {1,3,13,3,1,7,9,7,1,1}; // repeat last guy
  for (int i=0; i<9; ++i) {
    dot( (string) x[i], dir(40*i), dir(40*i), darkcyan);
    draw(dir(40*i)--dir(40*i+40), darkcyan);
    label( (string) (x[i] + x[i+1]),
    midpoint(dir(40*i)--dir(40*i+40)), dir(40*i+20), red);
  }
\end{asy}
\end{center}
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$:
\begin{center}
\begin{asy}
  size(4cm);
  int[] x = {13,3,1,1,3,13}; // repeat last guy
  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+36), red);
  }
\end{asy}
\end{center}

\begin{remark*}
  By applying the process of (a) in reverse,
  one essentially finds an inductive characterization
  of all expensive $n$-tuples.
\end{remark*}