I read about the following puzzle thirty-five years ago or so, and I still do not know the answer.

One gives an integer $n\ge1$ and asks to place the integers $1,2,\ldots,N=\frac{n(n+1)}{2}$ in a triangle according to the following rules. Each integer is used exactly once. There are $n$ integers on the first row, $n-1$ on the second one, ... and finally one in the $n$th row (the last one). The integers of the $j$th row are placed below the middle of intervals of the $(j-1)$th row. Finally, when $a$ and $b$ are neighbours in the $(j-1)$th row, and $c$ lies in $j$-th row, below the middle of $(a,b)$ (I say that $a$ and $b$ dominate $c$), then $c=|b-a|$.

Here is an example, with $n=4$. $$\begin{matrix} 6 & & 10 & & 1 & & 8 \\\\ & 4 & & 9 & & 7 \\\\ & & 5 & & 2 & & \\\\ & & & 3 & & & \end{matrix}$$

Does every know about this ? Is it related to something classical in mathematics ? Maybe eigenvalues of Hermitian matrices and their principal submatrices.

If I remember well, the author claimed that there are solutions for $n=1,2,3,4,5$, but not for $6$, and the existence was an open question when $n\ge7$. Can anyone confirm this ?

Trying to solve this problem, I soon was able to prove the following.

If a solution exists, then among the numbers $1,\ldots,n$, exactly one lies on each line, which is obviously the smallest in the line. In addition, the smallest of a line is a neighbour of the highest, and they dominate the highest of the next line.

The article perhaps appeared in the *Revue du Palais de la Découverte*.

**Edit**. Thanks to G. Myerson's answer, we know that these objects are called *Exact difference triangles* in the literature.

graceful labelingof a graph: en.wikipedia.org/wiki/Graceful_labeling . It seems your problem could be rephrased as gracefully labeling a particular graph. Not clear this would yield any insights, though... – Joseph O'Rourke Dec 1 '10 at 14:19