Applying the Pigeonhole Principle to a Set of Subsets
up vote
3
down vote
favorite
Let $A$ be a set of six positive integers each of which is less
than $15$. Show that there must be two distinct subsets of $A$ whose elements when added up give the same sum.
This is what I've tried so far.
There are $2 ^ 6 = 64$ subsets of $A$. We can also calculate the largest possible sum of a subset to be $14+13+12+11+10+9 = 69$. The smallest possible sum for a subset is $0$. Thus, there are $70$ possible sums, but only $63$ possible subsets $($assuming we exclude the empty set$)$. Is there something I am missing so that I can apply the pigeonhole principle?
probability discrete-mathematics pigeonhole-principle
edited Nov 18 at 16:12
Key Flex
7,04931229
asked Nov 18 at 2:29
Is12Prime
12619
add a comment |
up vote
3
down vote
favorite
Let $A$ be a set of six positive integers each of which is less
than $15$. Show that there must be two distinct subsets of $A$ whose elements when added up give the same sum.
This is what I've tried so far.
There are $2 ^ 6 = 64$ subsets of $A$. We can also calculate the largest possible sum of a subset to be $14+13+12+11+10+9 = 69$. The smallest possible sum for a subset is $0$. Thus, there are $70$ possible sums, but only $63$ possible subsets $($assuming we exclude the empty set$)$. Is there something I am missing so that I can apply the pigeonhole principle?
probability discrete-mathematics pigeonhole-principle
edited Nov 18 at 16:12
Key Flex
7,04931229
asked Nov 18 at 2:29
Is12Prime
12619
add a comment |
up vote
3
down vote
favorite
up vote
3
down vote
favorite
Let $A$ be a set of six positive integers each of which is less
than $15$. Show that there must be two distinct subsets of $A$ whose elements when added up give the same sum.
This is what I've tried so far.
There are $2 ^ 6 = 64$ subsets of $A$. We can also calculate the largest possible sum of a subset to be $14+13+12+11+10+9 = 69$. The smallest possible sum for a subset is $0$. Thus, there are $70$ possible sums, but only $63$ possible subsets $($assuming we exclude the empty set$)$. Is there something I am missing so that I can apply the pigeonhole principle?
probability discrete-mathematics pigeonhole-principle
edited Nov 18 at 16:12
Key Flex
7,04931229
asked Nov 18 at 2:29
Is12Prime
12619
Let $A$ be a set of six positive integers each of which is less
than $15$. Show that there must be two distinct subsets of $A$ whose elements when added up give the same sum.
This is what I've tried so far.
There are $2 ^ 6 = 64$ subsets of $A$. We can also calculate the largest possible sum of a subset to be $14+13+12+11+10+9 = 69$. The smallest possible sum for a subset is $0$. Thus, there are $70$ possible sums, but only $63$ possible subsets $($assuming we exclude the empty set$)$. Is there something I am missing so that I can apply the pigeonhole principle?
probability discrete-mathematics pigeonhole-principle
probability discrete-mathematics pigeonhole-principle
edited Nov 18 at 16:12
Key Flex
7,04931229
asked Nov 18 at 2:29
Is12Prime
12619
edited Nov 18 at 16:12
Key Flex
7,04931229
asked Nov 18 at 2:29
Is12Prime
12619
edited Nov 18 at 16:12
Key Flex
7,04931229
edited Nov 18 at 16:12
Key Flex
7,04931229
edited Nov 18 at 16:12
Key Flex
7,04931229
7,04931229
asked Nov 18 at 2:29
Is12Prime
12619
asked Nov 18 at 2:29
Is12Prime
12619
asked Nov 18 at 2:29
Is12Prime
12619
12619
add a comment |
add a comment |
2 Answers
2
active
oldest
votes
up vote
2
down vote
accepted
You're on the right track, but are indeed missing a few small things.
First, note that you can only get that highest possible sum of $69$ if $A ={ 9,10,11,12,13,14 }$. But any non-empty subset of that set has a sum of at least $9$, meaning that for any non-empty subset of this particular set, the sum of its members is at least $9$, and at most $69$, meaning that there are only $61$ possible sums for this subset, rather than $69$. Hence, the pigeonhole principle can be applied to this particular set.
OK, but how can we be sure the pigeonhole principle can be applied to any set $A$?
Well, note that the key observation we made regarding the specific set above was that the difference between the highest sum and lowest sum of non-empty subsets was $60$, and that was because that set contained the numbers $10$ through $14$. And now note that for any set, this difference between the highest and lowest set can never be greater than that, and is for most sets smaller than that.
So, we can say that for any set $A$, there are at most $61$ possible sums for the non-empty subsets of $A$, but there are $63$ non-empty subsets of $A$. So yes, the pigeonhole principle can be applied to any set $A$ to show that there must always be two subsets with the same sum.
answered Nov 18 at 2:45
Bram28
58.6k44185
@ Bram 28 Just to clarify, is my mistake that I assumed that there are 70 possible sums for all of the subsets of all possible sets A when I should have been considering the number of possible sums for a given set A?
– Is12Prime
Nov 18 at 2:51
1
@JohnRolding Exactly! Indeed, it is not enough show that the pigeonhole principle can be applied to this particular set with numbers $9$ through $14$, but that it can be applied to any set $A$.
– Bram28
Nov 18 at 2:57
add a comment |
up vote
2
down vote
Your approach is correct.
The largest possible sum for any subset must be $69$ since $69 = 14+ 13+ 12 + 11 + 10 + 9$.
The smallest possible sum is $0$ since all the integers are positive but we may take the empty set. Thus there are $70$ possible sums. We create a function from the subsets to the integers from $0$ to $69$. A subset gets mapped to the sum of its elements. There are $64$ possible subsets of a six element set.
Thus, since $64 < 70$, there doesn't exists a number which has two subsets mapped to it.
Therefore, there doesn't exists two subsets with the same sum.
To prove that there must be two distinct subsets of $A$ by using pigeonhole principle, then the sum of the of six positive integers should be less than $2^6=64$
answered Nov 18 at 2:41
Key Flex
7,04931229
add a comment |
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
2
down vote
accepted
You're on the right track, but are indeed missing a few small things.
First, note that you can only get that highest possible sum of $69$ if $A ={ 9,10,11,12,13,14 }$. But any non-empty subset of that set has a sum of at least $9$, meaning that for any non-empty subset of this particular set, the sum of its members is at least $9$, and at most $69$, meaning that there are only $61$ possible sums for this subset, rather than $69$. Hence, the pigeonhole principle can be applied to this particular set.
OK, but how can we be sure the pigeonhole principle can be applied to any set $A$?
Well, note that the key observation we made regarding the specific set above was that the difference between the highest sum and lowest sum of non-empty subsets was $60$, and that was because that set contained the numbers $10$ through $14$. And now note that for any set, this difference between the highest and lowest set can never be greater than that, and is for most sets smaller than that.
So, we can say that for any set $A$, there are at most $61$ possible sums for the non-empty subsets of $A$, but there are $63$ non-empty subsets of $A$. So yes, the pigeonhole principle can be applied to any set $A$ to show that there must always be two subsets with the same sum.
answered Nov 18 at 2:45
Bram28
58.6k44185
@ Bram 28 Just to clarify, is my mistake that I assumed that there are 70 possible sums for all of the subsets of all possible sets A when I should have been considering the number of possible sums for a given set A?
– Is12Prime
Nov 18 at 2:51
1
@JohnRolding Exactly! Indeed, it is not enough show that the pigeonhole principle can be applied to this particular set with numbers $9$ through $14$, but that it can be applied to any set $A$.
– Bram28
Nov 18 at 2:57
add a comment |
up vote
2
down vote
accepted
You're on the right track, but are indeed missing a few small things.
First, note that you can only get that highest possible sum of $69$ if $A ={ 9,10,11,12,13,14 }$. But any non-empty subset of that set has a sum of at least $9$, meaning that for any non-empty subset of this particular set, the sum of its members is at least $9$, and at most $69$, meaning that there are only $61$ possible sums for this subset, rather than $69$. Hence, the pigeonhole principle can be applied to this particular set.
OK, but how can we be sure the pigeonhole principle can be applied to any set $A$?
Well, note that the key observation we made regarding the specific set above was that the difference between the highest sum and lowest sum of non-empty subsets was $60$, and that was because that set contained the numbers $10$ through $14$. And now note that for any set, this difference between the highest and lowest set can never be greater than that, and is for most sets smaller than that.
So, we can say that for any set $A$, there are at most $61$ possible sums for the non-empty subsets of $A$, but there are $63$ non-empty subsets of $A$. So yes, the pigeonhole principle can be applied to any set $A$ to show that there must always be two subsets with the same sum.
answered Nov 18 at 2:45
Bram28
58.6k44185
@ Bram 28 Just to clarify, is my mistake that I assumed that there are 70 possible sums for all of the subsets of all possible sets A when I should have been considering the number of possible sums for a given set A?
– Is12Prime
Nov 18 at 2:51
1
@JohnRolding Exactly! Indeed, it is not enough show that the pigeonhole principle can be applied to this particular set with numbers $9$ through $14$, but that it can be applied to any set $A$.
– Bram28
Nov 18 at 2:57
add a comment |
up vote
2
down vote
accepted
up vote
2
down vote
accepted
You're on the right track, but are indeed missing a few small things.
First, note that you can only get that highest possible sum of $69$ if $A ={ 9,10,11,12,13,14 }$. But any non-empty subset of that set has a sum of at least $9$, meaning that for any non-empty subset of this particular set, the sum of its members is at least $9$, and at most $69$, meaning that there are only $61$ possible sums for this subset, rather than $69$. Hence, the pigeonhole principle can be applied to this particular set.
OK, but how can we be sure the pigeonhole principle can be applied to any set $A$?
Well, note that the key observation we made regarding the specific set above was that the difference between the highest sum and lowest sum of non-empty subsets was $60$, and that was because that set contained the numbers $10$ through $14$. And now note that for any set, this difference between the highest and lowest set can never be greater than that, and is for most sets smaller than that.
So, we can say that for any set $A$, there are at most $61$ possible sums for the non-empty subsets of $A$, but there are $63$ non-empty subsets of $A$. So yes, the pigeonhole principle can be applied to any set $A$ to show that there must always be two subsets with the same sum.
answered Nov 18 at 2:45
Bram28
58.6k44185
You're on the right track, but are indeed missing a few small things.
First, note that you can only get that highest possible sum of $69$ if $A ={ 9,10,11,12,13,14 }$. But any non-empty subset of that set has a sum of at least $9$, meaning that for any non-empty subset of this particular set, the sum of its members is at least $9$, and at most $69$, meaning that there are only $61$ possible sums for this subset, rather than $69$. Hence, the pigeonhole principle can be applied to this particular set.
OK, but how can we be sure the pigeonhole principle can be applied to any set $A$?
Well, note that the key observation we made regarding the specific set above was that the difference between the highest sum and lowest sum of non-empty subsets was $60$, and that was because that set contained the numbers $10$ through $14$. And now note that for any set, this difference between the highest and lowest set can never be greater than that, and is for most sets smaller than that.
So, we can say that for any set $A$, there are at most $61$ possible sums for the non-empty subsets of $A$, but there are $63$ non-empty subsets of $A$. So yes, the pigeonhole principle can be applied to any set $A$ to show that there must always be two subsets with the same sum.
answered Nov 18 at 2:45
Bram28
58.6k44185
edited Nov 18 at 13:12
answered Nov 18 at 2:45
Bram28
58.6k44185
answered Nov 18 at 2:45
Bram28
58.6k44185
answered Nov 18 at 2:45
Bram28
58.6k44185
58.6k44185
@ Bram 28 Just to clarify, is my mistake that I assumed that there are 70 possible sums for all of the subsets of all possible sets A when I should have been considering the number of possible sums for a given set A?
– Is12Prime
Nov 18 at 2:51
1
@JohnRolding Exactly! Indeed, it is not enough show that the pigeonhole principle can be applied to this particular set with numbers $9$ through $14$, but that it can be applied to any set $A$.
– Bram28
Nov 18 at 2:57
add a comment |
@ Bram 28 Just to clarify, is my mistake that I assumed that there are 70 possible sums for all of the subsets of all possible sets A when I should have been considering the number of possible sums for a given set A?
– Is12Prime
Nov 18 at 2:51
1
@JohnRolding Exactly! Indeed, it is not enough show that the pigeonhole principle can be applied to this particular set with numbers $9$ through $14$, but that it can be applied to any set $A$.
– Bram28
Nov 18 at 2:57
@ Bram 28 Just to clarify, is my mistake that I assumed that there are 70 possible sums for all of the subsets of all possible sets A when I should have been considering the number of possible sums for a given set A?
– Is12Prime
Nov 18 at 2:51
@ Bram 28 Just to clarify, is my mistake that I assumed that there are 70 possible sums for all of the subsets of all possible sets A when I should have been considering the number of possible sums for a given set A?
– Is12Prime
Nov 18 at 2:51
1
1
@JohnRolding Exactly! Indeed, it is not enough show that the pigeonhole principle can be applied to this particular set with numbers $9$ through $14$, but that it can be applied to any set $A$.
– Bram28
Nov 18 at 2:57
@JohnRolding Exactly! Indeed, it is not enough show that the pigeonhole principle can be applied to this particular set with numbers $9$ through $14$, but that it can be applied to any set $A$.
– Bram28
Nov 18 at 2:57
add a comment |
up vote
2
down vote
Your approach is correct.
The largest possible sum for any subset must be $69$ since $69 = 14+ 13+ 12 + 11 + 10 + 9$.
The smallest possible sum is $0$ since all the integers are positive but we may take the empty set. Thus there are $70$ possible sums. We create a function from the subsets to the integers from $0$ to $69$. A subset gets mapped to the sum of its elements. There are $64$ possible subsets of a six element set.
Thus, since $64 < 70$, there doesn't exists a number which has two subsets mapped to it.
Therefore, there doesn't exists two subsets with the same sum.
To prove that there must be two distinct subsets of $A$ by using pigeonhole principle, then the sum of the of six positive integers should be less than $2^6=64$
answered Nov 18 at 2:41
Key Flex
7,04931229
add a comment |
up vote
2
down vote
Your approach is correct.
The largest possible sum for any subset must be $69$ since $69 = 14+ 13+ 12 + 11 + 10 + 9$.
The smallest possible sum is $0$ since all the integers are positive but we may take the empty set. Thus there are $70$ possible sums. We create a function from the subsets to the integers from $0$ to $69$. A subset gets mapped to the sum of its elements. There are $64$ possible subsets of a six element set.
Thus, since $64 < 70$, there doesn't exists a number which has two subsets mapped to it.
Therefore, there doesn't exists two subsets with the same sum.
To prove that there must be two distinct subsets of $A$ by using pigeonhole principle, then the sum of the of six positive integers should be less than $2^6=64$
answered Nov 18 at 2:41
Key Flex
7,04931229
add a comment |
up vote
2
down vote
up vote
2
down vote
Your approach is correct.
The largest possible sum for any subset must be $69$ since $69 = 14+ 13+ 12 + 11 + 10 + 9$.
The smallest possible sum is $0$ since all the integers are positive but we may take the empty set. Thus there are $70$ possible sums. We create a function from the subsets to the integers from $0$ to $69$. A subset gets mapped to the sum of its elements. There are $64$ possible subsets of a six element set.
Thus, since $64 < 70$, there doesn't exists a number which has two subsets mapped to it.
Therefore, there doesn't exists two subsets with the same sum.
To prove that there must be two distinct subsets of $A$ by using pigeonhole principle, then the sum of the of six positive integers should be less than $2^6=64$
answered Nov 18 at 2:41
Key Flex
7,04931229
Your approach is correct.
The largest possible sum for any subset must be $69$ since $69 = 14+ 13+ 12 + 11 + 10 + 9$.
The smallest possible sum is $0$ since all the integers are positive but we may take the empty set. Thus there are $70$ possible sums. We create a function from the subsets to the integers from $0$ to $69$. A subset gets mapped to the sum of its elements. There are $64$ possible subsets of a six element set.
Thus, since $64 < 70$, there doesn't exists a number which has two subsets mapped to it.
Therefore, there doesn't exists two subsets with the same sum.
To prove that there must be two distinct subsets of $A$ by using pigeonhole principle, then the sum of the of six positive integers should be less than $2^6=64$
answered Nov 18 at 2:41
Key Flex
7,04931229
edited Nov 18 at 3:06
answered Nov 18 at 2:41
Key Flex
7,04931229
answered Nov 18 at 2:41
Key Flex
7,04931229
answered Nov 18 at 2:41
Key Flex
7,04931229
7,04931229
add a comment |
add a comment |
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Some of your past answers have not been well-received, and you're in danger of being blocked from answering.
Please pay close attention to the following guidance:
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
To learn more, see our tips on writing great answers.
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%2f3003076%2fapplying-the-pigeonhole-principle-to-a-set-of-subsets%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
