27
$\begingroup$

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.

$\endgroup$
4
  • 2
    $\begingroup$ This reminds me of graceful labeling of 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... $\endgroup$ Dec 1 '10 at 14:19
  • 1
    $\begingroup$ The problem reminds me of Ducci sequences : see en.wikipedia.org/wiki/Ducci_sequence $\endgroup$ Dec 1 '10 at 18:47
  • 1
    $\begingroup$ in all examples in every row the values never grow/fall twice. Can one proof this or is it just wrong ? $\endgroup$ Dec 2 '10 at 0:15
  • 1
    $\begingroup$ @HenrikRüping: the n=5 example with first row [6,14,15,3,13] shows this doesn't hold always. $\endgroup$
    – ndkrempel
    Dec 2 '10 at 1:08
28
$\begingroup$

This is the first problem in Chapter 9 of Martin Gardner, Penrose Tiles to Trapdoor Ciphers. In the addendum to the chapter, he writes that Herbert Taylor has proved it can't be done for $n\gt5$. Unfortunately, he gives no reference.

There may be something about the problem in Solomon W Golomb and Herbert Taylor, Cyclic projective planes, perfect circular rulers, and good spanning rulers, in Sequences and their applications (Bergen, 2001), 166–181, Discrete Math. Theor. Comput. Sci. (Lond.), Springer, London, 2002, MR1916130 (2003f:51016).

See also http://www.research.ibm.com/people/s/shearer/dts.html and the literature on difference matrices and difference triangles.

EDIT. Reading a little farther into the Gardner essay, I see he writes,

The only published proof known to me that the conjecture is true is given by G. J. Chang, M. C. Hu, K. W. Lih and T. C. Shieh in "Exact Difference Triangles," Bulletin of the Institute of Mathematics, Academia Sinica, Taipei, Taiwan (vol. 5, June 1977, pages 191- 197).

This paper can be found at http://w3.math.sinica.edu.tw/bulletin/bulletin_old/d51/5120.pdf and the review is MR0491218 (58 #10483).

$\endgroup$
10
$\begingroup$

For small values of $n$, there is a relatively small state space to search.

In the most naive way possible, I found the following (showing the top row of triangle only):

1: 1 way: [1]
2: 4 ways: [1,3], [2,3], [3,1], [3,2]
3: 8 ways: [1,6,4], [2,6,5], [4,1,6], [4,6,1], [5,2,6], [5,6,2], [6,1,4], [6,2,5]
4: 8 ways: [6,1,10,8], [6,10,1,8], [8,1,10,6], [8,3,10,9], [8,10,1,6], [8,10,3,9] [9,3,10,8], [9,10,3,8]
5: 2 ways: [6,14,15,3,13], [13,3,15,14,6]
6: no ways

In particular, it is possible for $n = 5$, but not possible for $n = 6$.

The computation for $n = 7$ seems entirely feasible, and I'm happy to carry it out.

$\endgroup$
6
  • 1
    $\begingroup$ Ok, using a slightly less naive search, I've shown there are none for n = 7 either. $\endgroup$
    – ndkrempel
    Dec 1 '10 at 22:08
  • 1
    $\begingroup$ Update: none for n = 8. That took about half an hour (using Ruby 1.9), so a more clever approach or faster language/computer may be required soon. $\endgroup$
    – ndkrempel
    Dec 1 '10 at 22:48
  • 1
    $\begingroup$ Since I set it running before more definitive answers came in, I may as well report there are none for n = 9 either, although that took about 6 hours (without improving the method). $\endgroup$
    – ndkrempel
    Dec 2 '10 at 5:56
  • 1
    $\begingroup$ Noting, that the biggest number must always be placed in the first row, the second biggest number in the first row or below a bigger number etc. should speed up the program a lot (if u didn't use that already). $\endgroup$ Dec 2 '10 at 10:14
  • 1
    $\begingroup$ @HenrikRüping: Thanks for that suggestion, the n=9 computation takes less than 4 minutes now. $\endgroup$
    – ndkrempel
    Dec 7 '10 at 18:35
2
$\begingroup$

Not an answer, but a question about constraints mod 2. There you are just taking differences, and the number 0s and 1s must be the same for n that is 0 or 3 mod 4 (one different in the other two cases). On the face of it the left edge of the triangle could be any binary sequence. Does this give anything?

$\endgroup$
1
  • $\begingroup$ It does indeed. For instance, for $n=5$, I got only two distinct (up to rotation) $(0,1)$ patterns. $\endgroup$ Dec 2 '10 at 0:44
2
$\begingroup$

From what I remember there is now an actual proof by 6 authors (one is Andy Liu); I think the paper was presented at g4g9. The paper might have not been published yet.

It is my understanding that Herbert Taylor was true but way to complicated, I think that Liu & et used his basic idea but simplified a lot the proof, which is now at an elementary level.

$\endgroup$
3
  • 1
    $\begingroup$ For the non-cognoscenti, g4g9 is the 9th Gathering for Gardner, held earlier this year. I couldn't find anything about this paper on their webpage, nor on Andy Liu's. I'm not suggesting Nick S is wrong, just reporting on the difficulty of finding anything. $\endgroup$ Dec 2 '10 at 22:50
  • $\begingroup$ Yea I couldn't find anything on Andy's page either and the g4g9 page doesn't contain any info on the speakers (they have the list from last year). But Andy gave a talk on this during the October 21st Celebration of Mind (see the Edmonton event). $\endgroup$
    – Nick S
    Dec 3 '10 at 6:14
  • $\begingroup$ I found the six-author paper. If you type Triangles of Absolute Differences - Art of Problem Solving into Google, most likely it will return a link you can click to get a pdf of the paper by Brian Chen et al. It's not clear to me whether the paper has ever been published in any other way. $\endgroup$ Jul 6 '19 at 23:09
1
$\begingroup$

So for n=6, we know we cannot achieve the same thing, but perhaps this is the next best top row?: [6,20,22,3,21,13]. We could say this difference triangle has ``excess one''. What is the smallest excess for n>6?

$\endgroup$
0
$\begingroup$

Trivially it is required that every positive integer from $1$ to $1+2+3+\cdots+2018$ appears exactly once.

Let $M_n$ denote the maximum number in the $n$th row and let $m_n$ denote the minimum number in the $n$th row.

Now assume $n\leq 2017$ and consider the numbers directly below $M_n$. Call these $a$ and $b$ where w.l.o.g. $a>b$. Then $a-b=M_n$. Since $a\leq M_{n+1}$ and $b\geq m_{n+1}$, we obtain that $M_{n+1}\geq M_n+m_{n+1}$.

Thus, for $1\leq i<j\leq 2018$, $$M_j\geq M_i+\sum_{k=i+1}^j m_i$$

In particular, since $M_1=m_1$, $$M_{2018}\geq \sum_{k=1}^{2018} m_k$$

Thus $M_{2018}$ is a sum of 2018 distinct positive integers. However, $M_{2018}\leq 1+2+3+\cdots+2018$. Thus $M_{2018}=1+2+3+\cdots+2018$ and $\{m_1,m_2,m_3,\dots,m_{2018}\}$ is a permutation of $\{1,2,3,\dots,2018\}$. Also, this implies that the other inequalities are also equalities and, for any $1\leq j\leq 2018$, $$M_j=\sum_{k=1}^j m_k$$

Now let any positive integer $n\leq 2018$ be "small" and let any positive integer $1+2+3+\cdots+2017\leq n\leq 1+2+3+\cdots+2018$ be "large". Since $\{m_1,m_2,m_3,\dots,m_{2018}\}$ is a permutation of $\{1,2,3,\dots,2018\}$, there is exactly one small number in each row.

If $n\leq 1954$, we have $$M_n=\sum_{k=1}^n m_k \leq 2018+2017+2016+\cdots+65$$ $$=(1+2+3+\cdots+2018)-(1+2+3+\cdots+64)$$ $$=(1+2+3+\cdots+2018)-2080$$ $$<1+2+3+\cdots+2017$$ so the $n$th row cannot contain any large numbers.

If $1955\leq n\leq 2017$, let $l$ be a large number in the $n$th row. Let the numbers directly below $l$ be $a$ and $b$ where w.l.o.g. $a>b$. We have $b=a-l$ and $a\leq 1+2+3+\cdots+2018$ so, because $l$ is large, $b\leq 2018$ so $b$ is small. Thus $b=m_{n+1}$ so $l$ is directly above $m_{n+1}$. Thus there are at most 2 large numbers in the $n$th row.

Thus there are at most 126 large numbers outside the bottom row. Since there are 2019 large numbers, there are at least 1893 large numbers in the bottom row so at most 125 non-large numbers in the bottom row. Now there are 2017 pairs of adjacent large numbers in the bottom row. We remove the pair directly beneath $m_{2017}$ and at most 250 other pairs containing a non-large number. Thus we can find a pair of adjacent large numbers in the bottom row, not directly beneath $m_{2017}$. However, their difference is small and in the 2017th row but not $m_{2017}$, which is a contradiction. Thus there is no such anti-Pascal triangle. See this imo 2018

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.