4

What finite ascending sequences of integers $(a_1, \cdots, a_n)$, with $a_1 = 0$, are such that the sequence obtained by sorting all the pairwise sums $a_i + a_j\;\;(j > i)$ consists of ${n \choose 2}$ distinct consecutive integers?

One example is the sequence $(0, 2, 3, 4)$, whose ${4 \choose 2} = 6$ pairwise sums (after sorting) make up the sequence of consecutive integers $(2, 3, 4, 5, 6, 7)$.

Are there longer sequences with this property?

kjo
  • 14,334
  • 1
    Need the sums be distinct for different summands? – Fimpellizzeri May 11 '16 at 00:43
  • @Fimpellizieri: yes; to put it differently, the sequence of summands should consist of ${n \choose 2}$ distinct consecutive integers. (I'll edit my question to make this clearer.) – kjo May 11 '16 at 00:44
  • 1
    Any maximal sequence is uniquely determined by the value of $a_2$. If $a_2\geq 3$ then $a_2,a_3,a_4,a_5$ must be consecutive, which violates the distinctness requirement, since then $a_2+a_5=a_3+a_4$, and therefore there are no longer sequences than $(0,2,3,4)$, which is the maximal sequence for $a_2=2$. The maximal sequence for $a_2=1$ is $(0,1,2,4)$. – Samuel May 11 '16 at 01:38
  • @Samuel: $(0,1,2,3)$ has two sums of $3$. – joriki May 11 '16 at 01:39
  • @joriki: Thanks, I meant (0,1,2,4). – Samuel May 11 '16 at 01:40
  • 1
    @Samuel: your comment looks like an answer to me. – kjo May 11 '16 at 01:48
  • 1
    @kjo: You can accept Fimpazirelli's answer. I wrote my comment as I was just heading to bed, so I was too lazy to write something with more details, and I didn't want to leave up an answer in case my sleep-deprived mind had made some silly mistake. – Samuel May 11 '16 at 09:40

1 Answers1

2

I think we can do it by exhaustion.

Suppose $a_2=1$. Then it must be that $a_3=2$ for the sequence must include the successor of $0+1$. At this point, the pairwise sums are $(1,2,3)$, so we would need to fill in the gap with $a_4=4$, yieding pairwise sums $(1,2,3,4,5,6)$. We would need to fill in the gap with $a_5=7$, but then our pairwise sums become $(1,2,3,4,5,6,7,8,9,11)$, which are not in sequence. Notice that one may not solve this by setting $a_6=10$ for then $11=1+10=4+7$ has two sums.

We can do a similar reasoning for other values of $a_2$. Consider the table:

\begin{array}{ccc} a_2 & \text{Sequence} & \text{Pairwise sums}\\ 1&(0,1,2,4)&1\text{ to } 6\\ 2&(0,2,3,4)&2\text{ to } 7\\ 3&(0,3)&3\\ 4&(0,4)&4 \end{array}

And I think you can see where this is going.

Claim: If $a_2\geq 3$, the longest such sequence is $(0,a_2)$.

Indeed, for one to continue the sequence we'd need to see $a_3=a_2+1$,and at this point the sequence of sums tentatively looks like $(a_2,a_2+1,2a_2+1)$. Since the sequence is ascending and $2a_2+1$ is the smallest sum of nonzero terms, if the sequence could be extended we'd need to fill in all the gaps, setting $a_3=a_2+2$, $a_4=a_2+3$, etc.

But then $3a_2=a_2+2a_2=(a_2+1)+(2a_2-1)$ has multiple sums, so the sequence cannot be extended. Notice this works because $a_2+1 \geq 4$ terms are defined this way, so that the minimum four distinct terms required for the multiple sums are always available.

Fimpellizzeri
  • 23,126
  • By the way, I spent a great deal of time trying to figure out how to make a table... Is there some alternative to tabular here? Something that could be used as separators here? – Fimpellizzeri May 11 '16 at 02:15