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
    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. – toliveira Oct 15 at 15:42
  • @toliveira While this is true, I do think the question is a bit more interesting if we assume the subvectors are not ordered. – Rushabh Mehta Oct 15 at 15:43
  • 1
    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'. – Mees de Vries Oct 15 at 15:44
  • @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. – felipa Oct 15 at 15:44
  • What are "some linear operations"? This is not obvious to me at all. – Mees de Vries Oct 15 at 15:46
up vote 14 down vote accepted

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

  • These perfect dice! – Parcly Taxel Oct 15 at 15:42
  • 1
    You can't? What about $(1, 3)$? – Mees de Vries Oct 15 at 15:49
  • Yes, you can make $4$ with the second vector, using the last two entries. – Ross Millikan Oct 15 at 15:50
  • @MeesdeVries You can take out 1 from both vectors and it still is a counterexample – Rushabh Mehta Oct 15 at 15:51
  • How confusing... something got updated since my comment. Nice counterexample! Thank you. – felipa Oct 15 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
    The reconstruction also gets $n$, the length of the original vector. – Mees de Vries Oct 15 at 15:47
  • Also: C = (1,1,1,2) and D = (1,1,1,1,1) And E = (1,1,2,1) – ypercubeᵀᴹ Oct 15 at 19:34
  • 1
    @ypercubeᵀᴹ Nope, the vectors have to be the same length. If not, $(1,1,1)$ and $(1,2)$ would be a counter example. – Rushabh Mehta Oct 15 at 19:34
  • Why make me think that the counter-example with smaller number of items and sum - if we consider that the order of the multiset matters - is (1,1,2) and (1,2,1). – ypercubeᵀᴹ Oct 15 at 19:35
  • Ah thnx. I missed the part that they have to have the same length. – ypercubeᵀᴹ Oct 15 at 19:36

Your Answer

 

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.