1
$\begingroup$

For each integer $n>1$, find a set of $n$ integers {$a_1, a_2, ..., a_n$} such that the set of numbers {$a_i + a_j | 1 \le i \le j \le n$} leave distinct remainders when divided by $n(n+1)/2$. If such set of integers does not exist, give a proof.

I know ideally I should show what I've attempted thus far but I'm completely lost and don't really know how to get started. I guess WLOG I can let $a_1 < a_2 <...<a_n$ and I also know that I should have from $0 \mod (n(n+1)/2)$ to $n(n+1)/2 - 1 \mod (n(n+1)/2)$ for $a_i + a_j$ but otherwise I'm not sure.

$\endgroup$
3
  • $\begingroup$ Not sure how much this helps, but you can further assume that $a_1=0$. $\endgroup$
    – Batominovski
    Jun 19, 2018 at 14:22
  • $\begingroup$ @Batominovski — wait how do you know that $a_1=0$? Could you explain further please $\endgroup$
    – space
    Jun 19, 2018 at 14:51
  • $\begingroup$ I said you can assume that $a_1=0$, I did not say that $a_1$ must be $0$. $\endgroup$
    – Batominovski
    Jun 19, 2018 at 14:53

1 Answer 1

Reset to default
1
$\begingroup$

There is no solution for $n=3$. We might as well assume $a_1=0$ as otherwise we can subtract $a_1$ from all the values and $2a_1$ from all the sums.
If $a_2=1$ we can form $0,1,2$ so $a_3$ must be $3,4, \text { or }5$ but $3+3\equiv 0 , 4+4\equiv 2,5+1 \equiv 0 \bmod 6$.
If $a_1=2$ we can form $0,2,4$ and $a_3+a_3$ will be one of these.
If $a_1=3$ we have $3+3\equiv 0 \bmod 6$.
That leaves $0,4,5$ but $5+5\equiv 0+4 \bmod 6$

I suspect one can modify the proof, which I do not know, that there are no perfect Golomb rulers of order greater than $4$ to show this problem cannot be solved either.

$\endgroup$
2
  • $\begingroup$ I know that $n=4$ does not work either, but so far, $n=1,2,3,4$ are the only numbers I know whether they work. $\endgroup$
    – Batominovski
    Jun 19, 2018 at 15:52
  • $\begingroup$ Another way of eliminating the $0,4,5$ case is to note that $4\equiv -2\bmod 6$ and we can multiply all the $a_i$ and all the sums by $-1$ to reduce to an existing case. $\endgroup$
    – Steven Stadnicki
    Jun 19, 2018 at 20:37

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .