With the pigeon hole principle how do you tell which are the pigeons and which are the holes?
up vote
3
down vote
favorite
For example, I was reading this example from my textbook:
Let S be a set of six positive integers who maximum is at most 14.
Show that the sums of the elements in all the nonempty subsets of S
cannot all be distinct.
For each nonempty subset A of S the sum of the elements in A denoted
$$S_A$$ satisfies $$1leq S_A leq 9+10+...+14=69$$ and there are $$2^6-1=63$$
nonempty subsets of S. We should like to draw the conclusion from the
pigeonhole principle by letting the possible sums, from 1 to 69 be the
pigeonholes with 63 nonempty subsets of S as the pigeons but then we
have too few pigeons.
Why can't you say that there are 63 pigeonholes and 69 pigeons?
discrete-mathematics pigeonhole-principle
asked Oct 31 '13 at 3:06
Celeritas
98311734
add a comment |
up vote
3
down vote
favorite
For example, I was reading this example from my textbook:
Let S be a set of six positive integers who maximum is at most 14.
Show that the sums of the elements in all the nonempty subsets of S
cannot all be distinct.
For each nonempty subset A of S the sum of the elements in A denoted
$$S_A$$ satisfies $$1leq S_A leq 9+10+...+14=69$$ and there are $$2^6-1=63$$
nonempty subsets of S. We should like to draw the conclusion from the
pigeonhole principle by letting the possible sums, from 1 to 69 be the
pigeonholes with 63 nonempty subsets of S as the pigeons but then we
have too few pigeons.
Why can't you say that there are 63 pigeonholes and 69 pigeons?
discrete-mathematics pigeonhole-principle
asked Oct 31 '13 at 3:06
Celeritas
98311734
I'm reminded of a sicker statement of the piegonhole principle: if you have $n$ pigeons and put $k$ holes in them, where $k > n$, then at least one pigeon will have at least two holes in it.
– Nate Eldredge
Oct 31 '13 at 3:15
add a comment |
up vote
3
down vote
favorite
up vote
3
down vote
favorite
For example, I was reading this example from my textbook:
Let S be a set of six positive integers who maximum is at most 14.
Show that the sums of the elements in all the nonempty subsets of S
cannot all be distinct.
For each nonempty subset A of S the sum of the elements in A denoted
$$S_A$$ satisfies $$1leq S_A leq 9+10+...+14=69$$ and there are $$2^6-1=63$$
nonempty subsets of S. We should like to draw the conclusion from the
pigeonhole principle by letting the possible sums, from 1 to 69 be the
pigeonholes with 63 nonempty subsets of S as the pigeons but then we
have too few pigeons.
Why can't you say that there are 63 pigeonholes and 69 pigeons?
discrete-mathematics pigeonhole-principle
asked Oct 31 '13 at 3:06
Celeritas
98311734
For example, I was reading this example from my textbook:
Let S be a set of six positive integers who maximum is at most 14.
Show that the sums of the elements in all the nonempty subsets of S
cannot all be distinct.
For each nonempty subset A of S the sum of the elements in A denoted
$$S_A$$ satisfies $$1leq S_A leq 9+10+...+14=69$$ and there are $$2^6-1=63$$
nonempty subsets of S. We should like to draw the conclusion from the
pigeonhole principle by letting the possible sums, from 1 to 69 be the
pigeonholes with 63 nonempty subsets of S as the pigeons but then we
have too few pigeons.
Why can't you say that there are 63 pigeonholes and 69 pigeons?
discrete-mathematics pigeonhole-principle
discrete-mathematics pigeonhole-principle
asked Oct 31 '13 at 3:06
Celeritas
98311734
asked Oct 31 '13 at 3:06
Celeritas
98311734
asked Oct 31 '13 at 3:06
Celeritas
98311734
asked Oct 31 '13 at 3:06
Celeritas
98311734
asked Oct 31 '13 at 3:06
Celeritas
98311734
98311734
I'm reminded of a sicker statement of the piegonhole principle: if you have $n$ pigeons and put $k$ holes in them, where $k > n$, then at least one pigeon will have at least two holes in it.
– Nate Eldredge
Oct 31 '13 at 3:15
add a comment |
I'm reminded of a sicker statement of the piegonhole principle: if you have $n$ pigeons and put $k$ holes in them, where $k > n$, then at least one pigeon will have at least two holes in it.
– Nate Eldredge
Oct 31 '13 at 3:15
I'm reminded of a sicker statement of the piegonhole principle: if you have $n$ pigeons and put $k$ holes in them, where $k > n$, then at least one pigeon will have at least two holes in it.
– Nate Eldredge
Oct 31 '13 at 3:15
I'm reminded of a sicker statement of the piegonhole principle: if you have $n$ pigeons and put $k$ holes in them, where $k > n$, then at least one pigeon will have at least two holes in it.
– Nate Eldredge
Oct 31 '13 at 3:15
add a comment |
2 Answers
2
active
oldest
votes
up vote
1
down vote
accepted
In this example you are putting the subsets of $S$ (which all have sums) and placing them into the sums of $1$ to $69$. Think of the sums of $S$ as bins, we only have $63$ non empty subsets, and $69$ bins to put them in.
answered Oct 31 '13 at 3:13
MITjanitor
1,9331343
add a comment |
up vote
0
down vote
When you are asked to show that "There are at least two $X$ with the same $Y$, then $X$ are usually the pigeons and $Y$ are usually the holes.
answered Nov 18 at 3:11
Ovi
12.1k938108
add a comment |
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
1
down vote
accepted
In this example you are putting the subsets of $S$ (which all have sums) and placing them into the sums of $1$ to $69$. Think of the sums of $S$ as bins, we only have $63$ non empty subsets, and $69$ bins to put them in.
answered Oct 31 '13 at 3:13
MITjanitor
1,9331343
add a comment |
up vote
1
down vote
accepted
In this example you are putting the subsets of $S$ (which all have sums) and placing them into the sums of $1$ to $69$. Think of the sums of $S$ as bins, we only have $63$ non empty subsets, and $69$ bins to put them in.
answered Oct 31 '13 at 3:13
MITjanitor
1,9331343
add a comment |
up vote
1
down vote
accepted
up vote
1
down vote
accepted
In this example you are putting the subsets of $S$ (which all have sums) and placing them into the sums of $1$ to $69$. Think of the sums of $S$ as bins, we only have $63$ non empty subsets, and $69$ bins to put them in.
answered Oct 31 '13 at 3:13
MITjanitor
1,9331343
In this example you are putting the subsets of $S$ (which all have sums) and placing them into the sums of $1$ to $69$. Think of the sums of $S$ as bins, we only have $63$ non empty subsets, and $69$ bins to put them in.
answered Oct 31 '13 at 3:13
MITjanitor
1,9331343
answered Oct 31 '13 at 3:13
MITjanitor
1,9331343
answered Oct 31 '13 at 3:13
MITjanitor
1,9331343
answered Oct 31 '13 at 3:13
MITjanitor
1,9331343
1,9331343
add a comment |
add a comment |
up vote
0
down vote
When you are asked to show that "There are at least two $X$ with the same $Y$, then $X$ are usually the pigeons and $Y$ are usually the holes.
answered Nov 18 at 3:11
Ovi
12.1k938108
add a comment |
up vote
0
down vote
When you are asked to show that "There are at least two $X$ with the same $Y$, then $X$ are usually the pigeons and $Y$ are usually the holes.
answered Nov 18 at 3:11
Ovi
12.1k938108
add a comment |
up vote
0
down vote
up vote
0
down vote
When you are asked to show that "There are at least two $X$ with the same $Y$, then $X$ are usually the pigeons and $Y$ are usually the holes.
answered Nov 18 at 3:11
Ovi
12.1k938108
When you are asked to show that "There are at least two $X$ with the same $Y$, then $X$ are usually the pigeons and $Y$ are usually the holes.
answered Nov 18 at 3:11
Ovi
12.1k938108
answered Nov 18 at 3:11
Ovi
12.1k938108
answered Nov 18 at 3:11
Ovi
12.1k938108
answered Nov 18 at 3:11
Ovi
12.1k938108
12.1k938108
add a comment |
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%2f546455%2fwith-the-pigeon-hole-principle-how-do-you-tell-which-are-the-pigeons-and-which-a%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
I'm reminded of a sicker statement of the piegonhole principle: if you have $n$ pigeons and put $k$ holes in them, where $k > n$, then at least one pigeon will have at least two holes in it.
– Nate Eldredge
Oct 31 '13 at 3:15