Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
add comment

2 Answers

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.

share|improve this answer
add comment

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}
share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.