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.

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.

share|improve this question
    
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$)? –  joriki Sep 24 '12 at 8:55
    
The list could include 0 but it doesn't have to. –  Jeff Sep 24 '12 at 8:55
    
Then I'd call them "non-negative integers". –  joriki Sep 24 '12 at 8:59
    
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. –  Jeff Sep 24 '12 at 8:59
    
The first sentence of the question is still ambiguous. –  joriki Sep 24 '12 at 9:53

1 Answer 1

up vote 1 down vote accepted

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$.

share|improve this answer

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.