Show that distinct subsets of a set have equal sums using pigeonhole principle
up vote
1
down vote
favorite
For $Ssubset{1,2,...,117}$ and $|S|=10$, I need to show that distinct such subsets have equal sums. That is, if $s_A$ is the sum of the elements in one 10-cardinality subset and $s_B$ is the sum of another, distinct 10-cardinality subset, 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 11:48
notadoctor
967
add a comment |
up vote
1
down vote
favorite
For $Ssubset{1,2,...,117}$ and $|S|=10$, I need to show that distinct such subsets have equal sums. That is, if $s_A$ is the sum of the elements in one 10-cardinality subset and $s_B$ is the sum of another, distinct 10-cardinality subset, 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 11:48
notadoctor
967
There are 117! subsets, and fewer than 117+116+115+114+113+112+111+110+109+108 possible sums.
– user3482749
Nov 16 at 11:52
I don't understand. The subsets $(underline {1,4},5,6,7,8,9,10,11,12)$ and $(underline {2,3},5,6,7,8,9,10,11,12)$ obviously have the same sum. Is that all you are asking?
– lulu
Nov 16 at 11:52
I think what you really are asking is to prove that $S$ has two distinct subsets with the same sum. Otherwise @lulu has the answer.
– Michal Adamaszek
Nov 16 at 12:07
Yes, that is indeed what I meant. I'll have to pose it as a separate problem.
– notadoctor
Nov 16 at 19:11
add a comment |
up vote
1
down vote
favorite
up vote
1
down vote
favorite
For $Ssubset{1,2,...,117}$ and $|S|=10$, I need to show that distinct such subsets have equal sums. That is, if $s_A$ is the sum of the elements in one 10-cardinality subset and $s_B$ is the sum of another, distinct 10-cardinality subset, 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 11:48
notadoctor
967
For $Ssubset{1,2,...,117}$ and $|S|=10$, I need to show that distinct such subsets have equal sums. That is, if $s_A$ is the sum of the elements in one 10-cardinality subset and $s_B$ is the sum of another, distinct 10-cardinality subset, 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 11:48
notadoctor
967
asked Nov 16 at 11:48
notadoctor
967
asked Nov 16 at 11:48
notadoctor
967
asked Nov 16 at 11:48
notadoctor
967
asked Nov 16 at 11:48
notadoctor
967
967
There are 117! subsets, and fewer than 117+116+115+114+113+112+111+110+109+108 possible sums.
– user3482749
Nov 16 at 11:52
I don't understand. The subsets $(underline {1,4},5,6,7,8,9,10,11,12)$ and $(underline {2,3},5,6,7,8,9,10,11,12)$ obviously have the same sum. Is that all you are asking?
– lulu
Nov 16 at 11:52
I think what you really are asking is to prove that $S$ has two distinct subsets with the same sum. Otherwise @lulu has the answer.
– Michal Adamaszek
Nov 16 at 12:07
Yes, that is indeed what I meant. I'll have to pose it as a separate problem.
– notadoctor
Nov 16 at 19:11
add a comment |
There are 117! subsets, and fewer than 117+116+115+114+113+112+111+110+109+108 possible sums.
– user3482749
Nov 16 at 11:52
I don't understand. The subsets $(underline {1,4},5,6,7,8,9,10,11,12)$ and $(underline {2,3},5,6,7,8,9,10,11,12)$ obviously have the same sum. Is that all you are asking?
– lulu
Nov 16 at 11:52
I think what you really are asking is to prove that $S$ has two distinct subsets with the same sum. Otherwise @lulu has the answer.
– Michal Adamaszek
Nov 16 at 12:07
Yes, that is indeed what I meant. I'll have to pose it as a separate problem.
– notadoctor
Nov 16 at 19:11
There are 117! subsets, and fewer than 117+116+115+114+113+112+111+110+109+108 possible sums.
– user3482749
Nov 16 at 11:52
There are 117! subsets, and fewer than 117+116+115+114+113+112+111+110+109+108 possible sums.
– user3482749
Nov 16 at 11:52
I don't understand. The subsets $(underline {1,4},5,6,7,8,9,10,11,12)$ and $(underline {2,3},5,6,7,8,9,10,11,12)$ obviously have the same sum. Is that all you are asking?
– lulu
Nov 16 at 11:52
I don't understand. The subsets $(underline {1,4},5,6,7,8,9,10,11,12)$ and $(underline {2,3},5,6,7,8,9,10,11,12)$ obviously have the same sum. Is that all you are asking?
– lulu
Nov 16 at 11:52
I think what you really are asking is to prove that $S$ has two distinct subsets with the same sum. Otherwise @lulu has the answer.
– Michal Adamaszek
Nov 16 at 12:07
I think what you really are asking is to prove that $S$ has two distinct subsets with the same sum. Otherwise @lulu has the answer.
– Michal Adamaszek
Nov 16 at 12:07
Yes, that is indeed what I meant. I'll have to pose it as a separate problem.
– notadoctor
Nov 16 at 19:11
Yes, that is indeed what I meant. I'll have to pose it as a separate problem.
– notadoctor
Nov 16 at 19:11
add a comment |
1 Answer
1
active
oldest
votes
up vote
2
down vote
accepted
For a subset of cardinality $10$, the smallest sum is $$1+2+3+...+10 =55$$ and the largest is $$108+109+...+117 = 1125$$
Therefore we have only $1125-54= 1071$ possible sums.
The number of such subsets is $binom {117}{10} approx 9times 10^{13}$ which is much higher the number of possible sums.
Thus we have many distinct sets with the same sums.
We can put more restrictions on subsets to make the problem challenging. For example asking sums and square sums being the same.
answered Nov 16 at 12:08
Mohammad Riazi-Kermani
40.3k41958
Yes, this is the obvious case. I misstated the problem initially, but the misstatement is so severe that it's not worth editing to fix, and I'll simply pose it as a separate problem. This answer is fine for the question as stated above.
– notadoctor
Nov 16 at 18:48
add a comment |
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
2
down vote
accepted
For a subset of cardinality $10$, the smallest sum is $$1+2+3+...+10 =55$$ and the largest is $$108+109+...+117 = 1125$$
Therefore we have only $1125-54= 1071$ possible sums.
The number of such subsets is $binom {117}{10} approx 9times 10^{13}$ which is much higher the number of possible sums.
Thus we have many distinct sets with the same sums.
We can put more restrictions on subsets to make the problem challenging. For example asking sums and square sums being the same.
answered Nov 16 at 12:08
Mohammad Riazi-Kermani
40.3k41958
Yes, this is the obvious case. I misstated the problem initially, but the misstatement is so severe that it's not worth editing to fix, and I'll simply pose it as a separate problem. This answer is fine for the question as stated above.
– notadoctor
Nov 16 at 18:48
add a comment |
up vote
2
down vote
accepted
For a subset of cardinality $10$, the smallest sum is $$1+2+3+...+10 =55$$ and the largest is $$108+109+...+117 = 1125$$
Therefore we have only $1125-54= 1071$ possible sums.
The number of such subsets is $binom {117}{10} approx 9times 10^{13}$ which is much higher the number of possible sums.
Thus we have many distinct sets with the same sums.
We can put more restrictions on subsets to make the problem challenging. For example asking sums and square sums being the same.
answered Nov 16 at 12:08
Mohammad Riazi-Kermani
40.3k41958
Yes, this is the obvious case. I misstated the problem initially, but the misstatement is so severe that it's not worth editing to fix, and I'll simply pose it as a separate problem. This answer is fine for the question as stated above.
– notadoctor
Nov 16 at 18:48
add a comment |
up vote
2
down vote
accepted
up vote
2
down vote
accepted
For a subset of cardinality $10$, the smallest sum is $$1+2+3+...+10 =55$$ and the largest is $$108+109+...+117 = 1125$$
Therefore we have only $1125-54= 1071$ possible sums.
The number of such subsets is $binom {117}{10} approx 9times 10^{13}$ which is much higher the number of possible sums.
Thus we have many distinct sets with the same sums.
We can put more restrictions on subsets to make the problem challenging. For example asking sums and square sums being the same.
answered Nov 16 at 12:08
Mohammad Riazi-Kermani
40.3k41958
For a subset of cardinality $10$, the smallest sum is $$1+2+3+...+10 =55$$ and the largest is $$108+109+...+117 = 1125$$
Therefore we have only $1125-54= 1071$ possible sums.
The number of such subsets is $binom {117}{10} approx 9times 10^{13}$ which is much higher the number of possible sums.
Thus we have many distinct sets with the same sums.
We can put more restrictions on subsets to make the problem challenging. For example asking sums and square sums being the same.
answered Nov 16 at 12:08
Mohammad Riazi-Kermani
40.3k41958
edited Nov 16 at 13:17
answered Nov 16 at 12:08
Mohammad Riazi-Kermani
40.3k41958
answered Nov 16 at 12:08
Mohammad Riazi-Kermani
40.3k41958
answered Nov 16 at 12:08
Mohammad Riazi-Kermani
40.3k41958
40.3k41958
Yes, this is the obvious case. I misstated the problem initially, but the misstatement is so severe that it's not worth editing to fix, and I'll simply pose it as a separate problem. This answer is fine for the question as stated above.
– notadoctor
Nov 16 at 18:48
add a comment |
Yes, this is the obvious case. I misstated the problem initially, but the misstatement is so severe that it's not worth editing to fix, and I'll simply pose it as a separate problem. This answer is fine for the question as stated above.
– notadoctor
Nov 16 at 18:48
Yes, this is the obvious case. I misstated the problem initially, but the misstatement is so severe that it's not worth editing to fix, and I'll simply pose it as a separate problem. This answer is fine for the question as stated above.
– notadoctor
Nov 16 at 18:48
Yes, this is the obvious case. I misstated the problem initially, but the misstatement is so severe that it's not worth editing to fix, and I'll simply pose it as a separate problem. This answer is fine for the question as stated above.
– notadoctor
Nov 16 at 18:48
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%2f3001049%2fshow-that-distinct-subsets-of-a-set-have-equal-sums-using-pigeonhole-principle%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
There are 117! subsets, and fewer than 117+116+115+114+113+112+111+110+109+108 possible sums.
– user3482749
Nov 16 at 11:52
I don't understand. The subsets $(underline {1,4},5,6,7,8,9,10,11,12)$ and $(underline {2,3},5,6,7,8,9,10,11,12)$ obviously have the same sum. Is that all you are asking?
– lulu
Nov 16 at 11:52
I think what you really are asking is to prove that $S$ has two distinct subsets with the same sum. Otherwise @lulu has the answer.
– Michal Adamaszek
Nov 16 at 12:07
Yes, that is indeed what I meant. I'll have to pose it as a separate problem.
– notadoctor
Nov 16 at 19:11