### 2147483648's blog

By 2147483648, history, 4 months ago, Problem statement: You are given an integer $N$ and the task is to output an integer sequence $a_1, \ldots, a_m$, such that $1 \leq a_i \leq N$ and $a_i + a_j \neq a_k + a_l$ for $i \neq j, k \neq l, (i,\ j) \neq (k,\ l)$ (i. e. all $\frac{m(m-1)}{2}$ pairwise sums should be different). The goal is to maximize $m$ — the length of resulting sequence.

This problem comes from RUCODE recent competition, it had a requirement for answer $m \geq \frac{\sqrt{N}}{2}$. Also there was a requirement for $a_i \neq a_j,\ i \neq j$, but in reality in makes almost no sense since if $m \geq 3$ and if $a_i == a_j$ for some $i \neq j$, than $a_k + a_i == a_k + a_j$ for any $k \neq i,\ k \neq j$. Since case $m < 3$ is obvious, we will further assume that all numbers in a sequence are different.

The solution to this problem comes from the fact that...

Spoiler

So, if we take largest prime $p$ that $2p ^ 2 + (p ^ 2 + 1) \bmod (2p) <= N$, we will get a sequence with $m \approx \sqrt{\frac{N}{2}} = \frac{\sqrt{N}}{\sqrt{2}} = lb_1(N)$, which is enough to solve the original problem.

Now there some interesting questions:

1. Can we get some upper bound for $m$?

2. How can we compute the longest possible (an optimal) sequence for some small $N$?

1). Since $a_i + a_j < 2N$, then by Dirichlet's principle we get $\frac{m(m-1)}{2} < 2N \Rightarrow m^2 < 4N \Rightarrow m < 2\sqrt{N}$. So our construction is $ub_1 = 2\sqrt{2} \approx 2.82$ times shorter than this upper bound.

2). I wrote a recursive bruteforce, it can find the optimal answer for $N = 64$ in about $10$ seconds.

Code

These questions brings us to some more challenging problems:

1. Can we improve aforementioned lower bound construction? Or write some code, which will build longer sequence with some bruteforce and pruning?

2. Can we improve above the algorithm for finding the optimal sequence? Maybe get some polynomial solution (or prove that it lies somewhere in NP class)?

3. Can we improve upper bound for $m$?

Really wanna find some answers on these questions, appreciate any of your thoughts!

UPD1: thanks to nor, we now have an upper bound $m < (1 + \varepsilon) \sqrt{N} = ub_2(N)$, which brings us to the $\underset{N \to \infty}{\lim}\dfrac{ub_2(N)}{lb_1(N)} = \sqrt{2} \approx 1.41$ which is a massive improvement! Proof can be found here. Turns out that this problem was researched even before the era of computers!  Comments (9)
 » 4 months ago, # | ← Rev. 2 →   Rewrite the condition as $a_i-a_k\neq a_l-a_j$. Then, there are $\binom m2$ possible differences, and each difference is only allowed to appear at most twice. Since the difference is between $1$ and $N-1$, the inequality $\binom m2\leq N-1$ must hold, which gives the bound $m\leq\sqrt{2(N-1)}$
•  » » Here is the table of answers for small values of N. SpoilerN = 1: 1 0 N = 2: 2 1 N = 3: 3 2 N = 4: 3 2 N = 5: 4 2 N = 6: 4 3 N = 7: 4 3 N = 8: 5 3 N = 9: 5 4 N = 10: 5 4 N = 11: 5 4 N = 12: 5 4 N = 13: 6 4 N = 14: 6 5 N = 15: 6 5 N = 16: 6 5 N = 17: 6 5 N = 18: 6 5 N = 19: 7 6 N = 20: 7 6 N = 21: 7 6 N = 22: 7 6 N = 23: 7 6 N = 24: 7 6 N = 25: 8 6 N = 26: 8 7 N = 27: 8 7 N = 28: 8 7 N = 29: 8 7 N = 30: 8 7 N = 31: 8 7 N = 32: 8 7 N = 33: 8 8 N = 34: 8 8 N = 35: 9 8 N = 36: 9 8 N = 37: 9 8 N = 38: 9 8 N = 39: 9 8 N = 40: 9 8 N = 41: 9 8 N = 42: 9 9 N = 43: 9 9 N = 44: 9 9 N = 45: 9 9 N = 46: 10 9 N = 47: 10 9 N = 48: 10 9 N = 49: 10 9 N = 50: 10 9 N = 51: 10 10 N = 52: 10 10 N = 53: 10 10 N = 54: 10 10 N = 55: 10 10 N = 56: 10 10 N = 57: 10 10 N = 58: 11 10 N = 59: 11 10 N = 60: 11 10 The first value is the optimal $m$, the second value is $\lfloor\sqrt{2(N-1)}\rfloor$. It seems that this upper bound doesn't work (at least for small N). Can you explain it on some examples? Like $N = 5$ (optimal answer $1\ 2\ 3\ 5$) or $N = 8$ (optimal answer $1\ 2\ 3\ 5\ 8$)? Why the difference can't be negative?
•  » » » Oh $\binom m2\leq N-1$ actually implies $m\leq\sqrt{2(N-1)}+1$, which seems to be correct.
•  » » » » Still not working for $N = 5,\ 8$, but $m \leq \sqrt{2N} + 1$ does the trick.
•  » » » » $(2m - 1)^2 = 4m(m - 1) + 1 \le 8(N - 1) + 1 = 8N - 7$, so $m \le \frac{1 + \sqrt{8N - 7}}{2}$, which is a stronger bound.@2147483648, can you post the sequence you recover for $N = 5, 8$? Something seems off.
•  » » » » » $1, 2, 3, 5$ for $N=5$ and $1, 2, 3, 5, 8$ for $N=8$.
•  » » » » » » Oh, in that case, Golomb rulers have a slightly different definition, my bad. For Golomb rulers, you are allowed to have $i = j$ or $k = l$ in the restriction, so these sequences are not valid Golomb rulers, since $1 + 3 = 2 + 2$.
 » The sequences you're talking about are called Golomb rulers. Funnily enough, I had set a problem on them quite a while back with a similar construction as yours, and someone pointed out to me that a similar problem was on the IMO Shortlist 2001 as N6 which also mentions your construction in the official solutions (and when I looked into it further, there was a reference to that problem being on a French TST even before that, with the same construction, and the construction dates back to Erdös and Turán, much before any of these contests).
•  » » Wow, huge thanks for the references! It's absolutely crazy that this problem was studied so long ago.