With the pigeon hole principle how do you tell which are the pigeons and which are the holes?
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
98811835
add a comment |
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
98811835
1
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
To flesh out a comment by user spd_25 posted as an answer. A more refined estimate for $S_A$ would allow the use of the pigeonhole principle here: The sum is minimum for the subset ${min S}$, and bounded above by $min S + 10 + 11 + 12 + 13 + 14$, i.e. $min S leq S_A leq 60 + min S$, which allows us to consider only 61 pigeonholes instead. See also math.stackexchange.com/q/2888844. (Maybe the textbook does go on to explain this after the quoted part.)
– epimorphic
Dec 2 '18 at 17:19
add a comment |
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
98811835
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
98811835
asked Oct 31 '13 at 3:06
Celeritas
98811835
asked Oct 31 '13 at 3:06
Celeritas
98811835
asked Oct 31 '13 at 3:06
Celeritas
98811835
asked Oct 31 '13 at 3:06
Celeritas
98811835
98811835
1
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
To flesh out a comment by user spd_25 posted as an answer. A more refined estimate for $S_A$ would allow the use of the pigeonhole principle here: The sum is minimum for the subset ${min S}$, and bounded above by $min S + 10 + 11 + 12 + 13 + 14$, i.e. $min S leq S_A leq 60 + min S$, which allows us to consider only 61 pigeonholes instead. See also math.stackexchange.com/q/2888844. (Maybe the textbook does go on to explain this after the quoted part.)
– epimorphic
Dec 2 '18 at 17:19
add a comment |
1
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
To flesh out a comment by user spd_25 posted as an answer. A more refined estimate for $S_A$ would allow the use of the pigeonhole principle here: The sum is minimum for the subset ${min S}$, and bounded above by $min S + 10 + 11 + 12 + 13 + 14$, i.e. $min S leq S_A leq 60 + min S$, which allows us to consider only 61 pigeonholes instead. See also math.stackexchange.com/q/2888844. (Maybe the textbook does go on to explain this after the quoted part.)
– epimorphic
Dec 2 '18 at 17:19
1
1
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
To flesh out a comment by user spd_25 posted as an answer. A more refined estimate for $S_A$ would allow the use of the pigeonhole principle here: The sum is minimum for the subset ${min S}$, and bounded above by $min S + 10 + 11 + 12 + 13 + 14$, i.e. $min S leq S_A leq 60 + min S$, which allows us to consider only 61 pigeonholes instead. See also math.stackexchange.com/q/2888844. (Maybe the textbook does go on to explain this after the quoted part.)
– epimorphic
Dec 2 '18 at 17:19
To flesh out a comment by user spd_25 posted as an answer. A more refined estimate for $S_A$ would allow the use of the pigeonhole principle here: The sum is minimum for the subset ${min S}$, and bounded above by $min S + 10 + 11 + 12 + 13 + 14$, i.e. $min S leq S_A leq 60 + min S$, which allows us to consider only 61 pigeonholes instead. See also math.stackexchange.com/q/2888844. (Maybe the textbook does go on to explain this after the quoted part.)
– epimorphic
Dec 2 '18 at 17:19
add a comment |
2 Answers
2
active
oldest
votes
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 |
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 '18 at 3:11
Ovi
12.4k1038111
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
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
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
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 |
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 |
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 |
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 '18 at 3:11
Ovi
12.4k1038111
add a comment |
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 '18 at 3:11
Ovi
12.4k1038111
add a comment |
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 '18 at 3:11
Ovi
12.4k1038111
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 '18 at 3:11
Ovi
12.4k1038111
answered Nov 18 '18 at 3:11
Ovi
12.4k1038111
answered Nov 18 '18 at 3:11
Ovi
12.4k1038111
answered Nov 18 '18 at 3:11
Ovi
12.4k1038111
12.4k1038111
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%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
1
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
To flesh out a comment by user spd_25 posted as an answer. A more refined estimate for $S_A$ would allow the use of the pigeonhole principle here: The sum is minimum for the subset ${min S}$, and bounded above by $min S + 10 + 11 + 12 + 13 + 14$, i.e. $min S leq S_A leq 60 + min S$, which allows us to consider only 61 pigeonholes instead. See also math.stackexchange.com/q/2888844. (Maybe the textbook does go on to explain this after the quoted part.)
– epimorphic
Dec 2 '18 at 17:19