1
$\begingroup$

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.

  • 0
    The first se$n$tence of the question is still ambiguous.2012-09-24

1 Answers 1

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