Can you determine a set of values from a set of sums?

722 Views Asked by At

Consider the following problem:

There is an vector $A$ (which you will not see) of $n$ positive integers. You are given the set of sums of the (contiguously indexed) subvectors of $A$. For example, say

$$A = (3,2,1,2)$$

The subvectors are $(3),(2),(1),(2), (3,2), (2,1), (1,2),(3,2,1), (2,1,2),(3,2,1,2)$. We would be given the sums $\{1, 2, 3, 5, 6, 8\}$. Let us call this set of sums $f(A)$.

Is it always possible to uniquely determine the set of integers in $A$ from $f(A)$ and $n$?


The answer turns out to be no. I posted a followup to When does a set of sums uniquely determine a set of values? .

2

There are 2 best solutions below

6
On BEST ANSWER

No: both $(1, 1, 2, 2)$ and $(1, 1, 1, 3)$ give you the set $\{1, 2, 3, 4, 5, 6\}$.

2
On

The answer is no.

Take the following subvectors:

$$A = (1, 1, 3)$$$$B = (1,2,2)$$It's easy to see that both vectors have a sum vector of $[1,2,3,4,5]$.