The problem: Consider some set containing n distinct integers. Now, say that we are now given the values of the n-choose-k sums attained by choosing k distinct elements from the n elements in the set and adding them all up. If we know the values of n and k, under what circumstances is it possible to uniquely determine the identity of the n- element set we started with?

  • $\begingroup$ So for example if the set is $\{1,2,4\}$ we have $n=3$ and if $k=2$ we are told "$n=3, k=2,$" sums are $\{3,5,6\}$, where the last may be a multiset and we are given the multiplicities? $\endgroup$ – Ross Millikan Mar 7 '13 at 0:51
  • $\begingroup$ Yes, exactly. It's clearly not too difficult to deduce the identity of the set for small values of k and n, but I haven't found any way to "scale up" the argument for larger values. $\endgroup$ – David Pechersky Mar 7 '13 at 1:03
  • $\begingroup$ I just wanted to make sure I was reading the problem correctly. $\endgroup$ – Ross Millikan Mar 7 '13 at 1:10

Consider the sets $A=\{1,4,5,6\}$ and $B=\{2,3,4,7\}$. Each has $n=4$ elements, and in each case the collection of pairwise sums (i.e. $k=2$) is $\{5,6,7,9,10,11\}$.

On the othjer hand, given four numbers and knowledge of the triple sums, one can find the four numbers since the four equations in four unknowns has nonzero determinant. So in case $n=4,\ k=3$ you can recover the set. (I think this works for any $n$ if $k=n-1$.)


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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