\magnification\magstephalf
\parskip 5pt
\def\adx#1:#2\par{\par\halign{\hskip #1##\hfill\cr #2}\par}

{\baselineskip14pt

{\bf Solution to Problem 10430.}\quad
[The problem should be amended to state that $a_1\leq \cdots\leq a_n$.
Otherwise there would be, for example, infinitely many dissimilar balanced
sequences $(0,-1,x,0)$ when $n=4$.]


Letting $d_j=a_{j+1}-a_j$, the (amended) problem for $n>2$ is equivalent to
finding a vector $d=(d_1,\ldots,d_{n-1})^T$ such that $ad=e$, where
$e=(1,\ldots,1)^T$ and $A$ is the $(n-1)\times(n-1)$ matrix having
$A_{ij}=\min(\vert i-j\vert,j,n-j)$. Let $A_i$ be row~$i$ of~$A$.

\medskip
{\bf Case 1}, $n$ is odd. Then we have $0=(2A_i-A_{i-1}-A_{i+1})\,
d=d_j-2d_i$, for $i=2j\bmod n$ and $1<i<n-1$. 
(Sketch of proof: If $0<\vert i-j\vert <\min(j,n-j)$, then
$A_{ij}-A_{(i+1)j}=A_{(i-1)j}-A_{ij}$; and when $\vert i-j\vert=\min(j,n-j)$ we
have $i=2j$ or $-i=n-2j$.)
Consider therefore the permutation $p(j)=2j\bmod n$ on $\{1,\ldots,n-1\}$, and
suppose $(1,2,2^2,\ldots,2^{k-1})$ is the cycle containing~1. If $n-1$ is not
in this cycle, there is another cycle $(n-1,n-2,n-2^2,\ldots,n-2^{k-1})$ and we
have
$$d_1=2d_2=4d_{2^2}=\cdots=2^{k-1}d_{2^{k-1}}=2^{k-1}x, \quad
d_{n-1}=2d_{n-2}=\cdots =2^{k-1}d_{n-2^{k-1}}=2^{k-1}y\,,$$
where $x=d_{(n+1)/2}$, $y=d_{(n-1)/2}$. Otherwise the cycle containing~1 is
$(1,2,\ldots,2^{k/2-1},n-1,\allowbreak 
n-2,\ldots,n-2^{k/2-1})$, and 
$$d_1=2d_2=\cdots=2^{k/2-1}d_{2^{k/2-1}}=2^{k/2-1}y\,,\quad
d_{n-1}=2d_{n-2}=\cdots=2^{k/2-1}d_{n-2^{k-1}}=2^{k/2-1}x\,.$$
If $(j,2j,\ldots,2^{l-1}j)$ is a cycle not containing 1 or $n-1$, we have
$d_j=d_{2j}=\cdots =d_{2^{l-1}j}=0$. Thus we have found nonnegative
integers~$b_j$ such that
$$d_j=b_jx+b_{n-j}y\,,\qquad b_jb_{n-j}=0\,,$$
for $1\leq j<n$. For example, when $n=15$ the cycles are $(1,2,4,8)(14,13,11,7)
(3,6,12,9)(5,10)$, and $(b_1,\ldots,b_{14})=
(8,4,0,2,0,0,0,1,0,0,0,0,0,0)$; when $n=11$ there is a single cycle
$(1,2,4,8,5,10$,
$9,7,3,6)$, and $(b_1,\ldots,b_{10})=(0,0,2,0,0,1,4,0,8,16)$.

We still must show that $x$ and $y$ are uniquely determined. This follows since
$1=A_1d=\sum_{j=1}^{n-1}\min(j-1,n-j)\,d_j=\alpha x+\beta y$ and
$1=A_{n-1}d=\sum_{j=1}^{n-1}\min(j,n-1-j)\,d_j=\beta x+\alpha y$, where
$\alpha\equiv(n-1)/2$ and $\beta\equiv(n+1)/2 \pmod 2$ because only
$b_{(n+1)/2}$ is odd. Hence $\alpha\neq \beta$.

\medskip
{\bf Case 2}, $n$ is even. Clearly $d_1=d_2=d_3={1\over 2}$ when $n=4$, so we
can assume that $n=2m$ where $(d'_1,\ldots,d'_{m-1})$ is the unique solution to
the equation $A'd'=e'$ in the case $n=m$. Now we find
$(2A_i-A_{i-1}-A_{i+1})\,d=-2d_i$ for all odd values of~$i$ in the range
$1<i<n-1$; hence $d_3=d_5=\cdots=d_{n-3}=0$. It follows that
$$A_{2i}\,d=\sum_{j=1}^{n-1}\min(\vert 2i-j\vert,j,n-j)\,d_j=d_1+d_{n-1}
+2\sum_{j=1}^{m-1}A'_{ij}\,d_{2j}\,,$$
for $1\leq i<m$. Let $x=d_1+d_{n-1}$; we know by induction that
$2d_{2j}=(1-x)\,d'_j$. Also the equations
$(A_1-A_2)\,d=(A_{n-2}-A_{n-1})\,d=0$ imply that
$$d_1=d_2+d_4+\cdots +d_{2\lfloor m/2\rfloor}\,,\qquad
d_{n-1}=d_{n-2}+d_{n-4}+\cdots +d_{2\lceil m/2\rceil}\,.$$
The induction hypothesis now tells us that $d'_j=d'_{m-j}$, hence
$d_1=d_{n-1}=x/2$. Finally, $x$~is determined by the relation
$$x=2d_2+\cdots +2d_{2\lfloor m/2\rfloor}=(1-x)(d'_1+\cdots +d'_{\lfloor
m/2\rfloor})\,.$$

Examination of this proof shows that a strictly increasing balanced sequence
exists for~$n$ if and only if $n=4$ or $n$ is prime and the order of 2
modulo~$n$ is $\geq (n-1)/2$; when $n\bmod 4=1$ we also require 
$2^{(n-1)/4}\bmod n\neq n-1$. The primes that do {\it not\/} satisfy the first
condition are $31,43,73,89,109,113,127,151,157,\ldots\,$; those that fail the
second are $17,41,97,137,193,\ldots\,$.

The proof also shows more: If $\gcd(j,n)$ is divisible by an odd prime, we have
$d_j=0$. If $n=2m+1$ has a strictly increasing balanced sequence of integers
$a_1<\cdots <a_n$, there is a permutation~$\pi$ of $\{0,\ldots,m-1\}$ such that
$(a_2-a_1,a_3-a_2,\ldots,a_n-a_{n-1})=(2^{\pi(0)},2^{\pi(1)},\ldots,
2^{\pi(m-1)}, 2^{\pi(m-1)},\ldots\,$, $2^{\pi(1)},2^{\pi(0)})c$ for
some positive integer~$c$.

The ratios of nonzero $d_j$ are not always powers of~2, however; the smallest
counterexample is $n=10$, when $(d_1,\ldots,d_9)=(3,2,0,1,0,1,0,2,3)c$.

}

\bigskip

\adx 275pt:
Donald E. Knuth\cr
Computer Science Department\cr
Stanford University\cr

\end
