Show that distinct subsets of a specific-cardinality subset have equal sums
up vote
1
down vote
favorite
For $Ssubset{1,2,...,117}$ and $|S|=10$, let $A$ and $B$ be distinct subsets of $S$. $s_A$ is the sum of the elements in $A$ and $s_B$ is the sum of those in $B$. How can I prove that there must be at least one such pair for which $s_A=s_B$?
I see that the pigeonhole principle is going to come in handy here through some comparison between the least and greatest possible sums, but I'm rusty on the exact methods for this technique.
combinatorics discrete-mathematics pigeonhole-principle
asked Nov 16 at 19:47
notadoctor
917
add a comment |
up vote
1
down vote
favorite
For $Ssubset{1,2,...,117}$ and $|S|=10$, let $A$ and $B$ be distinct subsets of $S$. $s_A$ is the sum of the elements in $A$ and $s_B$ is the sum of those in $B$. How can I prove that there must be at least one such pair for which $s_A=s_B$?
I see that the pigeonhole principle is going to come in handy here through some comparison between the least and greatest possible sums, but I'm rusty on the exact methods for this technique.
combinatorics discrete-mathematics pigeonhole-principle
asked Nov 16 at 19:47
notadoctor
917
This looks quite similar: Prove that there are two subsets of any cardinality-10 subsets of ${1,2dots,106}$ that sum to the same number, or this one: Any $B subset {10,11,...,99}$, with $|B| =10$ has two subsets such that $sum_{a in B_1} a = sum_{b in B_2} b$
– Martin R
Nov 16 at 19:55
Thanks, this does look very similar!
– notadoctor
Nov 16 at 20:03
Actually, I think this problem proves to be more difficult because the maximum sum is $1125$, which is greater than $2^{10}=1024$, the maximum number of 10-cardinality subsets.
– notadoctor
Nov 16 at 20:24
1
Hint; the maximum sum isn't $1125$. Since we exclude the empty set, the largest the sum could be is $117+116+cdots +109$. To be sure, if you don't exclude the empty set then you can just use $A=B=emptyset$...note that these are disjoint even though they coincide (as their intersection is empty).
– lulu
Nov 16 at 21:42
add a comment |
up vote
1
down vote
favorite
up vote
1
down vote
favorite
For $Ssubset{1,2,...,117}$ and $|S|=10$, let $A$ and $B$ be distinct subsets of $S$. $s_A$ is the sum of the elements in $A$ and $s_B$ is the sum of those in $B$. How can I prove that there must be at least one such pair for which $s_A=s_B$?
I see that the pigeonhole principle is going to come in handy here through some comparison between the least and greatest possible sums, but I'm rusty on the exact methods for this technique.
combinatorics discrete-mathematics pigeonhole-principle
asked Nov 16 at 19:47
notadoctor
917
For $Ssubset{1,2,...,117}$ and $|S|=10$, let $A$ and $B$ be distinct subsets of $S$. $s_A$ is the sum of the elements in $A$ and $s_B$ is the sum of those in $B$. How can I prove that there must be at least one such pair for which $s_A=s_B$?
I see that the pigeonhole principle is going to come in handy here through some comparison between the least and greatest possible sums, but I'm rusty on the exact methods for this technique.
combinatorics discrete-mathematics pigeonhole-principle
combinatorics discrete-mathematics pigeonhole-principle
asked Nov 16 at 19:47
notadoctor
917
asked Nov 16 at 19:47
notadoctor
917
edited Nov 16 at 19:53
asked Nov 16 at 19:47
notadoctor
917
asked Nov 16 at 19:47
notadoctor
917
asked Nov 16 at 19:47
notadoctor
917
917
This looks quite similar: Prove that there are two subsets of any cardinality-10 subsets of ${1,2dots,106}$ that sum to the same number, or this one: Any $B subset {10,11,...,99}$, with $|B| =10$ has two subsets such that $sum_{a in B_1} a = sum_{b in B_2} b$
– Martin R
Nov 16 at 19:55
Thanks, this does look very similar!
– notadoctor
Nov 16 at 20:03
Actually, I think this problem proves to be more difficult because the maximum sum is $1125$, which is greater than $2^{10}=1024$, the maximum number of 10-cardinality subsets.
– notadoctor
Nov 16 at 20:24
1
Hint; the maximum sum isn't $1125$. Since we exclude the empty set, the largest the sum could be is $117+116+cdots +109$. To be sure, if you don't exclude the empty set then you can just use $A=B=emptyset$...note that these are disjoint even though they coincide (as their intersection is empty).
– lulu
Nov 16 at 21:42
add a comment |
This looks quite similar: Prove that there are two subsets of any cardinality-10 subsets of ${1,2dots,106}$ that sum to the same number, or this one: Any $B subset {10,11,...,99}$, with $|B| =10$ has two subsets such that $sum_{a in B_1} a = sum_{b in B_2} b$
– Martin R
Nov 16 at 19:55
Thanks, this does look very similar!
– notadoctor
Nov 16 at 20:03
Actually, I think this problem proves to be more difficult because the maximum sum is $1125$, which is greater than $2^{10}=1024$, the maximum number of 10-cardinality subsets.
– notadoctor
Nov 16 at 20:24
1
Hint; the maximum sum isn't $1125$. Since we exclude the empty set, the largest the sum could be is $117+116+cdots +109$. To be sure, if you don't exclude the empty set then you can just use $A=B=emptyset$...note that these are disjoint even though they coincide (as their intersection is empty).
– lulu
Nov 16 at 21:42
This looks quite similar: Prove that there are two subsets of any cardinality-10 subsets of ${1,2dots,106}$ that sum to the same number, or this one: Any $B subset {10,11,...,99}$, with $|B| =10$ has two subsets such that $sum_{a in B_1} a = sum_{b in B_2} b$
– Martin R
Nov 16 at 19:55
This looks quite similar: Prove that there are two subsets of any cardinality-10 subsets of ${1,2dots,106}$ that sum to the same number, or this one: Any $B subset {10,11,...,99}$, with $|B| =10$ has two subsets such that $sum_{a in B_1} a = sum_{b in B_2} b$
– Martin R
Nov 16 at 19:55
Thanks, this does look very similar!
– notadoctor
Nov 16 at 20:03
Thanks, this does look very similar!
– notadoctor
Nov 16 at 20:03
Actually, I think this problem proves to be more difficult because the maximum sum is $1125$, which is greater than $2^{10}=1024$, the maximum number of 10-cardinality subsets.
– notadoctor
Nov 16 at 20:24
Actually, I think this problem proves to be more difficult because the maximum sum is $1125$, which is greater than $2^{10}=1024$, the maximum number of 10-cardinality subsets.
– notadoctor
Nov 16 at 20:24
1
1
Hint; the maximum sum isn't $1125$. Since we exclude the empty set, the largest the sum could be is $117+116+cdots +109$. To be sure, if you don't exclude the empty set then you can just use $A=B=emptyset$...note that these are disjoint even though they coincide (as their intersection is empty).
– lulu
Nov 16 at 21:42
Hint; the maximum sum isn't $1125$. Since we exclude the empty set, the largest the sum could be is $117+116+cdots +109$. To be sure, if you don't exclude the empty set then you can just use $A=B=emptyset$...note that these are disjoint even though they coincide (as their intersection is empty).
– lulu
Nov 16 at 21:42
add a comment |
1 Answer
1
active
oldest
votes
up vote
1
down vote
accepted
Suppose that $m$ is the smallest element of $S$. Let $t$ denote the sum of all elements of $S$. If $$t-m+1<2^{10}-1=1023,,text{ or equivalently }t-mleq 1021,,$$ then the claim follows, since there are $2^{10}-1$ nonempty subsets of $S$ whose element sums lie (inclusively) betweem $m$ and $t$. Now, prove that $t-mleq 1021$ must hold.
Well, we have $$t-mleq sumlimits_{k=0}^8,(117-k)=1017leq 1021,.$$ The statement is still true if we take $Ssubseteq {1,2,3,ldots,118}$ instead. This argument does not work any longer because $$sumlimits_{k=0}^8,(118-k)=1026>1021,.$$
However, note that if $S$ has four consecutive elements, then we are done. In the case that $S$ has no four consecutive elements, we have $$t-mleq 118+117+116+114+113+112+110+109+108=1017leq 1021,.$$ Therefore, the claim is still true. It is a bit more challenging to show that the statement is also true if we take $Ssubseteq {1,2,3,ldots,119}$. It would be interesting to find out the largest integer $k$ for which there exists $Ssubseteq {1,2,3,ldots,k}$ with $10$ elements such that no two nonempty subsets of $S$ have the same element sum.
answered Nov 16 at 22:17
Batominovski
31.8k23189
Thank you! I was able to solve it in a similar manner, but this is a much more robust proof. I'll mark it as the correct answer.
– notadoctor
Nov 17 at 4:36
add a comment |
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
1
down vote
accepted
Suppose that $m$ is the smallest element of $S$. Let $t$ denote the sum of all elements of $S$. If $$t-m+1<2^{10}-1=1023,,text{ or equivalently }t-mleq 1021,,$$ then the claim follows, since there are $2^{10}-1$ nonempty subsets of $S$ whose element sums lie (inclusively) betweem $m$ and $t$. Now, prove that $t-mleq 1021$ must hold.
Well, we have $$t-mleq sumlimits_{k=0}^8,(117-k)=1017leq 1021,.$$ The statement is still true if we take $Ssubseteq {1,2,3,ldots,118}$ instead. This argument does not work any longer because $$sumlimits_{k=0}^8,(118-k)=1026>1021,.$$
However, note that if $S$ has four consecutive elements, then we are done. In the case that $S$ has no four consecutive elements, we have $$t-mleq 118+117+116+114+113+112+110+109+108=1017leq 1021,.$$ Therefore, the claim is still true. It is a bit more challenging to show that the statement is also true if we take $Ssubseteq {1,2,3,ldots,119}$. It would be interesting to find out the largest integer $k$ for which there exists $Ssubseteq {1,2,3,ldots,k}$ with $10$ elements such that no two nonempty subsets of $S$ have the same element sum.
answered Nov 16 at 22:17
Batominovski
31.8k23189
Thank you! I was able to solve it in a similar manner, but this is a much more robust proof. I'll mark it as the correct answer.
– notadoctor
Nov 17 at 4:36
add a comment |
up vote
1
down vote
accepted
Suppose that $m$ is the smallest element of $S$. Let $t$ denote the sum of all elements of $S$. If $$t-m+1<2^{10}-1=1023,,text{ or equivalently }t-mleq 1021,,$$ then the claim follows, since there are $2^{10}-1$ nonempty subsets of $S$ whose element sums lie (inclusively) betweem $m$ and $t$. Now, prove that $t-mleq 1021$ must hold.
Well, we have $$t-mleq sumlimits_{k=0}^8,(117-k)=1017leq 1021,.$$ The statement is still true if we take $Ssubseteq {1,2,3,ldots,118}$ instead. This argument does not work any longer because $$sumlimits_{k=0}^8,(118-k)=1026>1021,.$$
However, note that if $S$ has four consecutive elements, then we are done. In the case that $S$ has no four consecutive elements, we have $$t-mleq 118+117+116+114+113+112+110+109+108=1017leq 1021,.$$ Therefore, the claim is still true. It is a bit more challenging to show that the statement is also true if we take $Ssubseteq {1,2,3,ldots,119}$. It would be interesting to find out the largest integer $k$ for which there exists $Ssubseteq {1,2,3,ldots,k}$ with $10$ elements such that no two nonempty subsets of $S$ have the same element sum.
answered Nov 16 at 22:17
Batominovski
31.8k23189
Thank you! I was able to solve it in a similar manner, but this is a much more robust proof. I'll mark it as the correct answer.
– notadoctor
Nov 17 at 4:36
add a comment |
up vote
1
down vote
accepted
up vote
1
down vote
accepted
Suppose that $m$ is the smallest element of $S$. Let $t$ denote the sum of all elements of $S$. If $$t-m+1<2^{10}-1=1023,,text{ or equivalently }t-mleq 1021,,$$ then the claim follows, since there are $2^{10}-1$ nonempty subsets of $S$ whose element sums lie (inclusively) betweem $m$ and $t$. Now, prove that $t-mleq 1021$ must hold.
Well, we have $$t-mleq sumlimits_{k=0}^8,(117-k)=1017leq 1021,.$$ The statement is still true if we take $Ssubseteq {1,2,3,ldots,118}$ instead. This argument does not work any longer because $$sumlimits_{k=0}^8,(118-k)=1026>1021,.$$
However, note that if $S$ has four consecutive elements, then we are done. In the case that $S$ has no four consecutive elements, we have $$t-mleq 118+117+116+114+113+112+110+109+108=1017leq 1021,.$$ Therefore, the claim is still true. It is a bit more challenging to show that the statement is also true if we take $Ssubseteq {1,2,3,ldots,119}$. It would be interesting to find out the largest integer $k$ for which there exists $Ssubseteq {1,2,3,ldots,k}$ with $10$ elements such that no two nonempty subsets of $S$ have the same element sum.
answered Nov 16 at 22:17
Batominovski
31.8k23189
Suppose that $m$ is the smallest element of $S$. Let $t$ denote the sum of all elements of $S$. If $$t-m+1<2^{10}-1=1023,,text{ or equivalently }t-mleq 1021,,$$ then the claim follows, since there are $2^{10}-1$ nonempty subsets of $S$ whose element sums lie (inclusively) betweem $m$ and $t$. Now, prove that $t-mleq 1021$ must hold.
Well, we have $$t-mleq sumlimits_{k=0}^8,(117-k)=1017leq 1021,.$$ The statement is still true if we take $Ssubseteq {1,2,3,ldots,118}$ instead. This argument does not work any longer because $$sumlimits_{k=0}^8,(118-k)=1026>1021,.$$
However, note that if $S$ has four consecutive elements, then we are done. In the case that $S$ has no four consecutive elements, we have $$t-mleq 118+117+116+114+113+112+110+109+108=1017leq 1021,.$$ Therefore, the claim is still true. It is a bit more challenging to show that the statement is also true if we take $Ssubseteq {1,2,3,ldots,119}$. It would be interesting to find out the largest integer $k$ for which there exists $Ssubseteq {1,2,3,ldots,k}$ with $10$ elements such that no two nonempty subsets of $S$ have the same element sum.
answered Nov 16 at 22:17
Batominovski
31.8k23189
edited Nov 16 at 22:33
answered Nov 16 at 22:17
Batominovski
31.8k23189
answered Nov 16 at 22:17
Batominovski
31.8k23189
answered Nov 16 at 22:17
Batominovski
31.8k23189
31.8k23189
Thank you! I was able to solve it in a similar manner, but this is a much more robust proof. I'll mark it as the correct answer.
– notadoctor
Nov 17 at 4:36
add a comment |
Thank you! I was able to solve it in a similar manner, but this is a much more robust proof. I'll mark it as the correct answer.
– notadoctor
Nov 17 at 4:36
Thank you! I was able to solve it in a similar manner, but this is a much more robust proof. I'll mark it as the correct answer.
– notadoctor
Nov 17 at 4:36
Thank you! I was able to solve it in a similar manner, but this is a much more robust proof. I'll mark it as the correct answer.
– notadoctor
Nov 17 at 4:36
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
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3001570%2fshow-that-distinct-subsets-of-a-specific-cardinality-subset-have-equal-sums%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
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
Required, but never shown
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
Required, but never shown
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
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
This looks quite similar: Prove that there are two subsets of any cardinality-10 subsets of ${1,2dots,106}$ that sum to the same number, or this one: Any $B subset {10,11,...,99}$, with $|B| =10$ has two subsets such that $sum_{a in B_1} a = sum_{b in B_2} b$
– Martin R
Nov 16 at 19:55
Thanks, this does look very similar!
– notadoctor
Nov 16 at 20:03
Actually, I think this problem proves to be more difficult because the maximum sum is $1125$, which is greater than $2^{10}=1024$, the maximum number of 10-cardinality subsets.
– notadoctor
Nov 16 at 20:24
1
Hint; the maximum sum isn't $1125$. Since we exclude the empty set, the largest the sum could be is $117+116+cdots +109$. To be sure, if you don't exclude the empty set then you can just use $A=B=emptyset$...note that these are disjoint even though they coincide (as their intersection is empty).
– lulu
Nov 16 at 21:42