Mixing
Can you determine a set of values from a set of sums?
Clash Royale CLAN TAG#URR8PPP
up vote
3
down vote
favorite
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$?
combinatorics
asked 2 hours ago
felipa
194117
add a comment |Â
up vote
3
down vote
favorite
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$?
combinatorics
asked 2 hours ago
felipa
194117
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
1 hour ago
@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
1 hour ago
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
1 hour ago
@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
1 hour ago
What are "some linear operations"? This is not obvious to me at all.
– Mees de Vries
1 hour ago
add a comment |Â
up vote
3
down vote
favorite
up vote
3
down vote
favorite
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$?
combinatorics
asked 2 hours ago
felipa
194117
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$?
combinatorics
combinatorics
asked 2 hours ago
felipa
194117
asked 2 hours ago
felipa
194117
asked 2 hours ago
felipa
194117
asked 2 hours ago
felipa
194117
asked 2 hours ago
felipa
194117
194117
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
1 hour ago
@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
1 hour ago
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
1 hour ago
@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
1 hour ago
What are "some linear operations"? This is not obvious to me at all.
– Mees de Vries
1 hour ago
add a comment |Â
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
1 hour ago
@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
1 hour ago
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
1 hour ago
@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
1 hour ago
What are "some linear operations"? This is not obvious to me at all.
– Mees de Vries
1 hour ago
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
1 hour ago
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
1 hour ago
@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
1 hour ago
@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
1 hour ago
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
1 hour ago
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
1 hour ago
@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
1 hour ago
@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
1 hour ago
What are "some linear operations"? This is not obvious to me at all.
– Mees de Vries
1 hour ago
What are "some linear operations"? This is not obvious to me at all.
– Mees de Vries
1 hour ago
add a comment |Â
2 Answers
2
active
oldest
votes
up vote
4
down vote
No: both $(1, 1, 2, 2)$ and $(1, 1, 1, 3)$ give you the set $1, 2, 3, 4, 5, 6$.
answered 1 hour ago
Mees de Vries
15.3k12451
These perfect dice!
– Parcly Taxel
1 hour ago
1
You can't? What about $(1, 3)$?
– Mees de Vries
1 hour ago
Yes, you can make $4$ with the second vector, using the last two entries.
– Ross Millikan
1 hour ago
@MeesdeVries You can take out 1 from both vectors and it still is a counterexample
– Rushabh Mehta
1 hour ago
How confusing... something got updated since my comment. Nice counterexample! Thank you.
– felipa
1 hour ago
add a comment |Â
up vote
3
down vote
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]$.
answered 1 hour ago
Rushabh Mehta
3,450228
1
The reconstruction also gets $n$, the length of the original vector.
– Mees de Vries
1 hour ago
add a comment |Â
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
4
down vote
No: both $(1, 1, 2, 2)$ and $(1, 1, 1, 3)$ give you the set $1, 2, 3, 4, 5, 6$.
answered 1 hour ago
Mees de Vries
15.3k12451
These perfect dice!
– Parcly Taxel
1 hour ago
1
You can't? What about $(1, 3)$?
– Mees de Vries
1 hour ago
Yes, you can make $4$ with the second vector, using the last two entries.
– Ross Millikan
1 hour ago
@MeesdeVries You can take out 1 from both vectors and it still is a counterexample
– Rushabh Mehta
1 hour ago
How confusing... something got updated since my comment. Nice counterexample! Thank you.
– felipa
1 hour ago
add a comment |Â
up vote
4
down vote
No: both $(1, 1, 2, 2)$ and $(1, 1, 1, 3)$ give you the set $1, 2, 3, 4, 5, 6$.
answered 1 hour ago
Mees de Vries
15.3k12451
These perfect dice!
– Parcly Taxel
1 hour ago
1
You can't? What about $(1, 3)$?
– Mees de Vries
1 hour ago
Yes, you can make $4$ with the second vector, using the last two entries.
– Ross Millikan
1 hour ago
@MeesdeVries You can take out 1 from both vectors and it still is a counterexample
– Rushabh Mehta
1 hour ago
How confusing... something got updated since my comment. Nice counterexample! Thank you.
– felipa
1 hour ago
add a comment |Â
up vote
4
down vote
up vote
4
down vote
No: both $(1, 1, 2, 2)$ and $(1, 1, 1, 3)$ give you the set $1, 2, 3, 4, 5, 6$.
answered 1 hour ago
Mees de Vries
15.3k12451
No: both $(1, 1, 2, 2)$ and $(1, 1, 1, 3)$ give you the set $1, 2, 3, 4, 5, 6$.
answered 1 hour ago
Mees de Vries
15.3k12451
answered 1 hour ago
Mees de Vries
15.3k12451
answered 1 hour ago
Mees de Vries
15.3k12451
answered 1 hour ago
Mees de Vries
15.3k12451
15.3k12451
These perfect dice!
– Parcly Taxel
1 hour ago
1
You can't? What about $(1, 3)$?
– Mees de Vries
1 hour ago
Yes, you can make $4$ with the second vector, using the last two entries.
– Ross Millikan
1 hour ago
@MeesdeVries You can take out 1 from both vectors and it still is a counterexample
– Rushabh Mehta
1 hour ago
How confusing... something got updated since my comment. Nice counterexample! Thank you.
– felipa
1 hour ago
add a comment |Â
These perfect dice!
– Parcly Taxel
1 hour ago
1
You can't? What about $(1, 3)$?
– Mees de Vries
1 hour ago
Yes, you can make $4$ with the second vector, using the last two entries.
– Ross Millikan
1 hour ago
@MeesdeVries You can take out 1 from both vectors and it still is a counterexample
– Rushabh Mehta
1 hour ago
How confusing... something got updated since my comment. Nice counterexample! Thank you.
– felipa
1 hour ago
These perfect dice!
– Parcly Taxel
1 hour ago
These perfect dice!
– Parcly Taxel
1 hour ago
1
1
You can't? What about $(1, 3)$?
– Mees de Vries
1 hour ago
You can't? What about $(1, 3)$?
– Mees de Vries
1 hour ago
Yes, you can make $4$ with the second vector, using the last two entries.
– Ross Millikan
1 hour ago
Yes, you can make $4$ with the second vector, using the last two entries.
– Ross Millikan
1 hour ago
@MeesdeVries You can take out 1 from both vectors and it still is a counterexample
– Rushabh Mehta
1 hour ago
@MeesdeVries You can take out 1 from both vectors and it still is a counterexample
– Rushabh Mehta
1 hour ago
How confusing... something got updated since my comment. Nice counterexample! Thank you.
– felipa
1 hour ago
How confusing... something got updated since my comment. Nice counterexample! Thank you.
– felipa
1 hour ago
add a comment |Â
up vote
3
down vote
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]$.
answered 1 hour ago
Rushabh Mehta
3,450228
1
The reconstruction also gets $n$, the length of the original vector.
– Mees de Vries
1 hour ago
add a comment |Â
up vote
3
down vote
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]$.
answered 1 hour ago
Rushabh Mehta
3,450228
1
The reconstruction also gets $n$, the length of the original vector.
– Mees de Vries
1 hour ago
add a comment |Â
up vote
3
down vote
up vote
3
down vote
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]$.
answered 1 hour ago
Rushabh Mehta
3,450228
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]$.
answered 1 hour ago
Rushabh Mehta
3,450228
edited 1 hour ago
answered 1 hour ago
Rushabh Mehta
3,450228
answered 1 hour ago
Rushabh Mehta
3,450228
answered 1 hour ago
Rushabh Mehta
3,450228
3,450228
1
The reconstruction also gets $n$, the length of the original vector.
– Mees de Vries
1 hour ago
add a comment |Â
1
The reconstruction also gets $n$, the length of the original vector.
– Mees de Vries
1 hour ago
1
1
The reconstruction also gets $n$, the length of the original vector.
– Mees de Vries
1 hour ago
The reconstruction also gets $n$, the length of the original vector.
– Mees de Vries
1 hour ago
add a comment |Â
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2956667%2fcan-you-determine-a-set-of-values-from-a-set-of-sums%23new-answer', 'question_page');
);
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
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
1 hour ago
@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
1 hour ago
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
1 hour ago
@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
1 hour ago
What are "some linear operations"? This is not obvious to me at all.
– Mees de Vries
1 hour ago