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.
Deducing a list of natural numbers from the list of sums
1
$\begingroup$
combinatorics
-
0Does "including $0$" refer to the natural numbers (i.e. the list *can* include $0$) or to the list (i.e. the list includes $0$)? – 2012-09-24
-
0The list could include 0 but it doesn't have to. – 2012-09-24
-
0Then I'd call them "non-negative integers". – 2012-09-24
-
0I 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. – 2012-09-24
-
0The first sentence of the question is still ambiguous. – 2012-09-24
1 Answers
2
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$.