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
    $\begingroup$ I understand that the vector is ordered, while the set of sums is not. So B=(2,1,2,3) is different from A, but f(A)=f(B). In this case, the answer is no. $\endgroup$ – toliveira Oct 15 '18 at 15:42
  • $\begingroup$ @toliveira While this is true, I do think the question is a bit more interesting if we assume the subvectors are not ordered. $\endgroup$ – Don Thousand Oct 15 '18 at 15:43
  • 1
    $\begingroup$ I accidentally read the question wrong initially, and I am interested in the version where you get a multiset of sums instead of just a set. Did you consider that question @felipa? Edit: and possibly you also want to reconstruct the multiset $A$, rather than just its 'set version'. $\endgroup$ – Mees de Vries Oct 15 '18 at 15:44
  • $\begingroup$ @toliveira The question is about determining the set of integers in $A$ which is $\{1,2,3\}$. Your $B$ has the same set of integers. So in your case I don't think we know the answer is no. $\endgroup$ – felipa Oct 15 '18 at 15:44
  • $\begingroup$ What are "some linear operations"? This is not obvious to me at all. $\endgroup$ – Mees de Vries Oct 15 '18 at 15:46

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

  • $\begingroup$ These perfect dice! $\endgroup$ – Parcly Taxel Oct 15 '18 at 15:42
  • 1
    $\begingroup$ You can't? What about $(1, 3)$? $\endgroup$ – Mees de Vries Oct 15 '18 at 15:49
  • $\begingroup$ Yes, you can make $4$ with the second vector, using the last two entries. $\endgroup$ – Ross Millikan Oct 15 '18 at 15:50
  • $\begingroup$ @MeesdeVries You can take out 1 from both vectors and it still is a counterexample $\endgroup$ – Don Thousand Oct 15 '18 at 15:51
  • $\begingroup$ How confusing... something got updated since my comment. Nice counterexample! Thank you. $\endgroup$ – felipa Oct 15 '18 at 15:52

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

  • 1
    $\begingroup$ The reconstruction also gets $n$, the length of the original vector. $\endgroup$ – Mees de Vries Oct 15 '18 at 15:47
  • 1
    $\begingroup$ @ypercubeᵀᴹ Nope, the vectors have to be the same length. If not, $(1,1,1)$ and $(1,2)$ would be a counter example. $\endgroup$ – Don Thousand Oct 15 '18 at 19:34

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.