7
$\begingroup$

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

$\endgroup$
5
  • 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, 2018 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$ Oct 15, 2018 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$ Oct 15, 2018 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$
    – graffe
    Oct 15, 2018 at 15:44
  • $\begingroup$ What are "some linear operations"? This is not obvious to me at all. $\endgroup$ Oct 15, 2018 at 15:46

2 Answers 2

14
$\begingroup$

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

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

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

$\endgroup$
2
  • 1
    $\begingroup$ The reconstruction also gets $n$, the length of the original vector. $\endgroup$ Oct 15, 2018 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$ Oct 15, 2018 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.