Let $S$ be a list of k natural numbers (including 0). Let $S'$ be another such list. Each such list gives way to a list of $2^k$ sums of its members. Can $S$ be recovered if I'm given the list of its $2^k$ sums? Progress so far: you can read a minimum element of $S$ by reading a minimum element of its list of sums. You can read a maximum element of $S$ by taking the top two of its sums and subtracting. You can read off the sum of every element by looking at the maximum element in the list of sums. Thus, you can also recover the sum of every element in S without one copy of the min and one copy of the max.

  • $\begingroup$ Does "including $0$" refer to the natural numbers (i.e. the list can include $0$) or to the list (i.e. the list includes $0$)? $\endgroup$ – joriki Sep 24 '12 at 8:55
  • $\begingroup$ The list could include 0 but it doesn't have to. $\endgroup$ – Jeff Sep 24 '12 at 8:55
  • $\begingroup$ Then I'd call them "non-negative integers". $\endgroup$ – joriki Sep 24 '12 at 8:59
  • $\begingroup$ I suspect that here the natural numbers could be replaced by the integers, rationals, reals, or complex numbers. Perhaps it could even be replaced by any commutative monoid with a cancellation law. Please answer in as much generality as possible, although anything that works even for the stated case in the original problem above will suffice for what I need. $\endgroup$ – Jeff Sep 24 '12 at 8:59
  • $\begingroup$ The first sentence of the question is still ambiguous. $\endgroup$ – joriki Sep 24 '12 at 9:53

At each stage of the algorithm, add a least element of the list of sums to the list of numbers and then remove all sums of this element with all combinations of elements that were already in the list of numbers from the list of sums. That is, if $S$ is the multiset of sums and $L$ is the multiset of numbers, start with $L_0=\emptyset$ and $S_0=S$ and apply

$$ \begin{align} L_{n+1}&=L_n\cup\{\min S_n\}\;,\\ S_{n+1}&=S_n\setminus\left\{\min S_n+\sum_{t\in T}t\mid T\subseteq L_n\right\} \end{align} $$

to obtain $L=L_k$.


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.