An interesting problem about distinct pairwise sums.

Revision en2, by 2147483648, 2023-05-28 01:23:02

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). And our 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 realtily in makes almost no sense since if $$$m \geq 3$$$ and $$$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 sase $$$m < 3$$$ is obvious, we further assume that all numbers in 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}}$$$, 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$$$?

Here are my humble answers:

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 $$$2\sqrt{2} \approx 2.82$$$ times shorter than this upper bound. Can you improve 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 for 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 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 want to find some answers on these questions, so feel free to comment!

Tags distinct pairwise sums, constructive algorithms, interesting problem, tag

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en17 English 2147483648 2023-05-28 06:09:16 0 (published)
en16 English 2147483648 2023-05-28 06:08:57 419 Tiny change: 'm < (1 + \epsilon) \' -> 'm < (1 + \varepsilon) \' (saved to drafts)
en15 English 2147483648 2023-05-28 01:34:09 0 (published)
en14 English 2147483648 2023-05-28 01:33:19 42
en13 English 2147483648 2023-05-28 01:32:03 4 Tiny change: 'ove above algorith' -> 'ove above the algorith'
en12 English 2147483648 2023-05-28 01:31:01 2 Tiny change: ' < 2\sqrt{n}$. So our' -> ' < 2\sqrt{N}$. So our'
en11 English 2147483648 2023-05-28 01:29:27 3 Tiny change: 'brings us for some more' -> 'brings us to some more'
en10 English 2147483648 2023-05-28 01:28:29 2 Tiny change: 'answers:\n1). Sinc' -> 'answers:\n\n1). Sinc'
en9 English 2147483648 2023-05-28 01:28:04 36
en8 English 2147483648 2023-05-28 01:26:49 2 Tiny change: 'umbers in sequence ' -> 'umbers in a sequence '
en7 English 2147483648 2023-05-28 01:26:23 5 Tiny change: 'vious, we further a' -> 'vious, we will further a'
en6 English 2147483648 2023-05-28 01:26:06 2 Tiny change: 'j$. Since sase $m < 3' -> 'j$. Since case $m < 3'
en5 English 2147483648 2023-05-28 01:25:26 3 Tiny change: 'eq 3$ and $a_i == a' -> 'eq 3$ and if $a_i == a'
en4 English 2147483648 2023-05-28 01:25:00 3 Tiny change: 'ut in realtily in makes' -> 'ut in reality in makes'
en3 English 2147483648 2023-05-28 01:23:53 10 Tiny change: 'fferent). And our goal is t' -> 'fferent). The goal is t'
en2 English 2147483648 2023-05-28 01:23:02 22 Tiny change: 'You are gi' -> 'Problem statement: You are gi'
en1 English 2147483648 2023-05-28 01:22:30 3108 Initial revision (saved to drafts)