5
$\begingroup$

Consider the set $(s_1, ..., s_N) \in S$, where all $s_i$ are positive integers selected from some interval $[M, L]$ and the sum of any $k$ integers in $S$ is required to be unique and to have a distance of at least $d$ from all other possible sums of $k$ integers in the set. For example, if $k = 2$, the sum of any two randomly chosen elements, i.e. $s_a$ and $s_b$, must generate a unique sum that has a difference of at least $d$ from all other possible sums of two elements in $S$.

As a function of $k$, the minimum difference between sums $d$, and the size of the interval, $(L - M)$, what is the largest possible size of the set $S$, and what is the most efficient way to compute its elements?

Edit - I'm of course happy to hear any $d = 1$ solutions.

Edit 2 - For the $d=1$ case, is this problem NP-complete, similar to the subset-sum problem?

2 Answers 2

1

Here's a start. The number of choices of $k$ elements is $N\choose k$ (or a little more, if repeats are allowed), and each sum is between $kM$ and $kL$, so you must have ${N\choose k}\lt kL-kM+2$ which gives you an upper bound on $N$. It doesn't tell you whether you can achieve that bound, nor an efficient way to try.

EDIT: Ah, you've changed the problem, so my answer is now relevant only to your case $d=1$. But if you divide the right side of the displayed inequality by $d$, it should apply to your more general question.

0

This is an algorithm that I am convinced is optimal, although I have not tried to prove it. First of all, we may assume that $L=0$ (consider ${s_1-L,\dots,s_N-L}$). For the algorithm I will describe, we may also asume that $d=1$.

The key is to observe that if $\{s_1,\dots,s_N\}$ is such that all sums of subsets of $k$ elements are different, so must be the sums of subsets of $m$ elements for $1\le m\le k$. This implies that $\{s_1,\dots,s_k\}$ must be the first $k$ terms of the sequence A005255. Let $n>k$ and suppose that $\{s_1,\dots,s_n\}$ is such that the sums of the subsets of $m$ elements are all different for $1\le m\le k$. Then we choose $s_{n+1}$ in such a way that for each $m$, $1\le m\le k$, the smallest possible sum of $m$ elements, one of them beeing $s_{n+1}$, is equal to the largest possible sum of $m$ terms in $\{s_1,\dots,s_n\}$ plus $1$. If the $s_j$'s are ordered in increasing order, this means $ s_{n+1}=\max_{1\le m\le k}\Bigl(\,\sum_{j=n-m+1}^ns_j-\sum_{j=1}^{m-1}s_j\Bigr)+1. $ It is easy to show that for all $n>k$ $ \sum_{j=n-k}^{n-1}s_j-\sum_{j=1}^{k-1}s_j\le s_n\le2\,s_{n-1}. $ In particular $s_n$ is almost like $2^n$.

For $d>1$, the algorithm will give $d$ times the solution with $d=1$.

The algorithm is implemented in the following Mathematica ce; you have to provide the values of $k$ and $M$.

k = 5; M = 1000000; s[1] = 0; s[2] = 1; s[n_Integer] :=    s[n] = Max[     Table[Sum[s[j], {j, n - m, n - 1}] - Sum[s[j], {j, m - 1}] +        1, {m, n - 1}]]; sol = Table[s[j], {j, k}]; If[Last[sol] <= S,   While[next =      Max[Table[       Total[Take[sol, -m]] - Total[Take[sol, m - 1]] + 1, {m, k}]];     next <= S, AppendTo[sol, next]]; Print[sol],    Print["M is too small; try again with a larger M"]] {0,1,2,4,7,13,24,46,88,172,337,661,1298,2550,5012,9852,19367,38073,74848,147146,289280,568708}