A standard and rigorous proof using the pigeonhole principle

The name of the pictureThe name of the pictureThe name of the pictureClash Royale CLAN TAG#URR8PPP











up vote
5
down vote

favorite
1












Now there is a question:



For twenty two-digit numbers, we add two digits together. (like 12 and get the result 3) Prove in these twenty numbers, there must be at least 2 same results.



Now I know I can assume the most extreme example which is adding 0,0 0,1 until 9,9, so I have at most 19 results. Therefore, the twentieth must be as same as one of the previous 19 ones.



But actually, I don't know the standard and rigorous proof of this problem. Can anyone help me with this standard proof?










share|cite|improve this question























  • You need to take a little care how you express yourself. The twentieth need not be the same as one of the previous ones - rather two must give the same result. Which of the sums are are equal depends on the numbers and their order. If I take the numbers from $80$ to $99$ there are plenty of pairs equal, but the last has sum $18$ which is not the same as any of the others.
    – Mark Bennet
    13 hours ago










  • If you're talking about the rigorous general proof that, for $n$ elements to be distributed into $d$ containers, at least one container has $lceil n/drceil$ elements, assume otherwise then prove a contradiction.
    – user496634
    13 hours ago










  • @MarkBennet Ok, My expression is not very rigorous. My example is the most extreme one.
    – An Yan
    13 hours ago










  • I don't think "00" counts as a two-digit number. So there are really only 18 possibilities.
    – Wildcard
    5 hours ago














up vote
5
down vote

favorite
1












Now there is a question:



For twenty two-digit numbers, we add two digits together. (like 12 and get the result 3) Prove in these twenty numbers, there must be at least 2 same results.



Now I know I can assume the most extreme example which is adding 0,0 0,1 until 9,9, so I have at most 19 results. Therefore, the twentieth must be as same as one of the previous 19 ones.



But actually, I don't know the standard and rigorous proof of this problem. Can anyone help me with this standard proof?










share|cite|improve this question























  • You need to take a little care how you express yourself. The twentieth need not be the same as one of the previous ones - rather two must give the same result. Which of the sums are are equal depends on the numbers and their order. If I take the numbers from $80$ to $99$ there are plenty of pairs equal, but the last has sum $18$ which is not the same as any of the others.
    – Mark Bennet
    13 hours ago










  • If you're talking about the rigorous general proof that, for $n$ elements to be distributed into $d$ containers, at least one container has $lceil n/drceil$ elements, assume otherwise then prove a contradiction.
    – user496634
    13 hours ago










  • @MarkBennet Ok, My expression is not very rigorous. My example is the most extreme one.
    – An Yan
    13 hours ago










  • I don't think "00" counts as a two-digit number. So there are really only 18 possibilities.
    – Wildcard
    5 hours ago












up vote
5
down vote

favorite
1









up vote
5
down vote

favorite
1






1





Now there is a question:



For twenty two-digit numbers, we add two digits together. (like 12 and get the result 3) Prove in these twenty numbers, there must be at least 2 same results.



Now I know I can assume the most extreme example which is adding 0,0 0,1 until 9,9, so I have at most 19 results. Therefore, the twentieth must be as same as one of the previous 19 ones.



But actually, I don't know the standard and rigorous proof of this problem. Can anyone help me with this standard proof?










share|cite|improve this question















Now there is a question:



For twenty two-digit numbers, we add two digits together. (like 12 and get the result 3) Prove in these twenty numbers, there must be at least 2 same results.



Now I know I can assume the most extreme example which is adding 0,0 0,1 until 9,9, so I have at most 19 results. Therefore, the twentieth must be as same as one of the previous 19 ones.



But actually, I don't know the standard and rigorous proof of this problem. Can anyone help me with this standard proof?







combinatorics pigeonhole-principle






share|cite|improve this question















share|cite|improve this question













share|cite|improve this question




share|cite|improve this question








edited 7 mins ago









Ari Brodsky

302211




302211










asked 14 hours ago









An Yan

435




435











  • You need to take a little care how you express yourself. The twentieth need not be the same as one of the previous ones - rather two must give the same result. Which of the sums are are equal depends on the numbers and their order. If I take the numbers from $80$ to $99$ there are plenty of pairs equal, but the last has sum $18$ which is not the same as any of the others.
    – Mark Bennet
    13 hours ago










  • If you're talking about the rigorous general proof that, for $n$ elements to be distributed into $d$ containers, at least one container has $lceil n/drceil$ elements, assume otherwise then prove a contradiction.
    – user496634
    13 hours ago










  • @MarkBennet Ok, My expression is not very rigorous. My example is the most extreme one.
    – An Yan
    13 hours ago










  • I don't think "00" counts as a two-digit number. So there are really only 18 possibilities.
    – Wildcard
    5 hours ago
















  • You need to take a little care how you express yourself. The twentieth need not be the same as one of the previous ones - rather two must give the same result. Which of the sums are are equal depends on the numbers and their order. If I take the numbers from $80$ to $99$ there are plenty of pairs equal, but the last has sum $18$ which is not the same as any of the others.
    – Mark Bennet
    13 hours ago










  • If you're talking about the rigorous general proof that, for $n$ elements to be distributed into $d$ containers, at least one container has $lceil n/drceil$ elements, assume otherwise then prove a contradiction.
    – user496634
    13 hours ago










  • @MarkBennet Ok, My expression is not very rigorous. My example is the most extreme one.
    – An Yan
    13 hours ago










  • I don't think "00" counts as a two-digit number. So there are really only 18 possibilities.
    – Wildcard
    5 hours ago















You need to take a little care how you express yourself. The twentieth need not be the same as one of the previous ones - rather two must give the same result. Which of the sums are are equal depends on the numbers and their order. If I take the numbers from $80$ to $99$ there are plenty of pairs equal, but the last has sum $18$ which is not the same as any of the others.
– Mark Bennet
13 hours ago




You need to take a little care how you express yourself. The twentieth need not be the same as one of the previous ones - rather two must give the same result. Which of the sums are are equal depends on the numbers and their order. If I take the numbers from $80$ to $99$ there are plenty of pairs equal, but the last has sum $18$ which is not the same as any of the others.
– Mark Bennet
13 hours ago












If you're talking about the rigorous general proof that, for $n$ elements to be distributed into $d$ containers, at least one container has $lceil n/drceil$ elements, assume otherwise then prove a contradiction.
– user496634
13 hours ago




If you're talking about the rigorous general proof that, for $n$ elements to be distributed into $d$ containers, at least one container has $lceil n/drceil$ elements, assume otherwise then prove a contradiction.
– user496634
13 hours ago












@MarkBennet Ok, My expression is not very rigorous. My example is the most extreme one.
– An Yan
13 hours ago




@MarkBennet Ok, My expression is not very rigorous. My example is the most extreme one.
– An Yan
13 hours ago












I don't think "00" counts as a two-digit number. So there are really only 18 possibilities.
– Wildcard
5 hours ago




I don't think "00" counts as a two-digit number. So there are really only 18 possibilities.
– Wildcard
5 hours ago










3 Answers
3






active

oldest

votes

















up vote
11
down vote



accepted










The pigeonhole principle says that if $i$ items are to be placed into $c$ containers, where $i>c$, then at least one container must have at least two items. The sums of the 20 numbers stand for 20 items and the number of possible results, 19, stands for the containers.






share|cite|improve this answer






















  • The application of the principle accomplishes the proof.
    – Wuestenfux
    13 hours ago






  • 1




    So you mean the most extreme example is there are 20 pigeons and 19 holes, so there must be two pigeons in the same holes?
    – An Yan
    13 hours ago










  • Right. This is the case.
    – Wuestenfux
    13 hours ago










  • OK, I see, thank you very much
    – An Yan
    13 hours ago

















up vote
18
down vote













The Pigeonhole Principle is really the statement that for finite sets $S,T$ with $|S|>|T|$, there is no injective mapping from $S$ to $T$. Proceed by induction on $|T|$. For $|T|=1$, $|S|ge 2$ by hypothesis; there is one map from $S$ to $T$ and it is not one-to-one. Now suppose true for sets with $n$ elements and that $|T|=n+1$ (and $|S|>n+1$), and let $phi:Sto T$. Let $tin T$. Then as there are no injective mappings from $S$ to $T-t$ by the induction hypothesis, $phi$ won't be injective unless some $sin S$ maps to $t$, so suppose this is so. If another element also maps to $T$, then clearly $phi$ is not one-to-one, so suppose that $phi^-1(t) = s$. Then $phi|_S-s$ maps $S-s$ to $T-t$, and by the induction hypothesis this map can't be one-to-one. So in all cases $phi$ fails to be one-to-one.






share|cite|improve this answer






















  • Sorry, because of short of knowledge of math, I cannot understand completely, But anyway, thank you very much for your help.
    – An Yan
    13 hours ago







  • 2




    While I'm sorry to be critical of this post, it is disappointing to me that the most upvoted answer (at this time) is one that gets an "A" grade in how to do math, but only gets a "D" grade in how to explain math to others. Know your audience and keep it simple are key principles in teaching.
    – Paul Sinclair
    8 hours ago






  • 10




    @PaulSinclair It's really because OP was confusing - the title and body of the question are different. The question in the body - answered by the accepted answer - is "How do I apply the pigeonhole principle", while the question in the title - answered here - is "How do I prove the pigeonhole principle". These not only necessitate different answers, but also imply different audiences. While the other answer works for OP, it would be a disappointment to anyone who found the question by title alone if it didn't have this answer.
    – Ordous
    7 hours ago










  • @Ordous Thank you.
    – John Brevik
    5 hours ago






  • 1




    @PaulSinclair I thought the OP was looking for a proof of the Pigeonhole Principle. I don't see why you needed to take a swipe at me for trying to help.
    – John Brevik
    5 hours ago

















up vote
3
down vote













I don't like quoting the pigeonhole principle when it is nothing more than common sense. Like this:




There are only $19$ possible two-digit sums, because the smallest is $0+0$ and the largest is $9+9$ and there are only $19$ integers from $0$ to $18$. So obviously if you have $20$ two-digit numbers, they cannot all have different digit sums, because $20 > 19$.




More generally, if you have $c·k+1$ items and assign one of $c$ labels to each item, there is a label assigned to at least $k+1$ items. Proof: If the claim is false, then every label is assigned to at most $k$ items, so there can be at most $c·k$ items, contradicting the given number of items. Therefore the claim is true.






share|cite|improve this answer




















  • Of course, translating this 'common sense' into formal rigorous reasoning is possible (such as in higher-order arithmetic or ZFC set theory), but it is not instructive at this level, because the intrinsic reasoning will be obscured.
    – user21820
    11 hours ago










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',
convertImagesToLinks: true,
noModals: false,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
);



);













 

draft saved


draft discarded


















StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2949860%2fa-standard-and-rigorous-proof-using-the-pigeonhole-principle%23new-answer', 'question_page');

);

Post as a guest






























3 Answers
3






active

oldest

votes








3 Answers
3






active

oldest

votes









active

oldest

votes






active

oldest

votes








up vote
11
down vote



accepted










The pigeonhole principle says that if $i$ items are to be placed into $c$ containers, where $i>c$, then at least one container must have at least two items. The sums of the 20 numbers stand for 20 items and the number of possible results, 19, stands for the containers.






share|cite|improve this answer






















  • The application of the principle accomplishes the proof.
    – Wuestenfux
    13 hours ago






  • 1




    So you mean the most extreme example is there are 20 pigeons and 19 holes, so there must be two pigeons in the same holes?
    – An Yan
    13 hours ago










  • Right. This is the case.
    – Wuestenfux
    13 hours ago










  • OK, I see, thank you very much
    – An Yan
    13 hours ago














up vote
11
down vote



accepted










The pigeonhole principle says that if $i$ items are to be placed into $c$ containers, where $i>c$, then at least one container must have at least two items. The sums of the 20 numbers stand for 20 items and the number of possible results, 19, stands for the containers.






share|cite|improve this answer






















  • The application of the principle accomplishes the proof.
    – Wuestenfux
    13 hours ago






  • 1




    So you mean the most extreme example is there are 20 pigeons and 19 holes, so there must be two pigeons in the same holes?
    – An Yan
    13 hours ago










  • Right. This is the case.
    – Wuestenfux
    13 hours ago










  • OK, I see, thank you very much
    – An Yan
    13 hours ago












up vote
11
down vote



accepted







up vote
11
down vote



accepted






The pigeonhole principle says that if $i$ items are to be placed into $c$ containers, where $i>c$, then at least one container must have at least two items. The sums of the 20 numbers stand for 20 items and the number of possible results, 19, stands for the containers.






share|cite|improve this answer














The pigeonhole principle says that if $i$ items are to be placed into $c$ containers, where $i>c$, then at least one container must have at least two items. The sums of the 20 numbers stand for 20 items and the number of possible results, 19, stands for the containers.







share|cite|improve this answer














share|cite|improve this answer



share|cite|improve this answer








edited 13 hours ago

























answered 14 hours ago









Wuestenfux

1,577139




1,577139











  • The application of the principle accomplishes the proof.
    – Wuestenfux
    13 hours ago






  • 1




    So you mean the most extreme example is there are 20 pigeons and 19 holes, so there must be two pigeons in the same holes?
    – An Yan
    13 hours ago










  • Right. This is the case.
    – Wuestenfux
    13 hours ago










  • OK, I see, thank you very much
    – An Yan
    13 hours ago
















  • The application of the principle accomplishes the proof.
    – Wuestenfux
    13 hours ago






  • 1




    So you mean the most extreme example is there are 20 pigeons and 19 holes, so there must be two pigeons in the same holes?
    – An Yan
    13 hours ago










  • Right. This is the case.
    – Wuestenfux
    13 hours ago










  • OK, I see, thank you very much
    – An Yan
    13 hours ago















The application of the principle accomplishes the proof.
– Wuestenfux
13 hours ago




The application of the principle accomplishes the proof.
– Wuestenfux
13 hours ago




1




1




So you mean the most extreme example is there are 20 pigeons and 19 holes, so there must be two pigeons in the same holes?
– An Yan
13 hours ago




So you mean the most extreme example is there are 20 pigeons and 19 holes, so there must be two pigeons in the same holes?
– An Yan
13 hours ago












Right. This is the case.
– Wuestenfux
13 hours ago




Right. This is the case.
– Wuestenfux
13 hours ago












OK, I see, thank you very much
– An Yan
13 hours ago




OK, I see, thank you very much
– An Yan
13 hours ago










up vote
18
down vote













The Pigeonhole Principle is really the statement that for finite sets $S,T$ with $|S|>|T|$, there is no injective mapping from $S$ to $T$. Proceed by induction on $|T|$. For $|T|=1$, $|S|ge 2$ by hypothesis; there is one map from $S$ to $T$ and it is not one-to-one. Now suppose true for sets with $n$ elements and that $|T|=n+1$ (and $|S|>n+1$), and let $phi:Sto T$. Let $tin T$. Then as there are no injective mappings from $S$ to $T-t$ by the induction hypothesis, $phi$ won't be injective unless some $sin S$ maps to $t$, so suppose this is so. If another element also maps to $T$, then clearly $phi$ is not one-to-one, so suppose that $phi^-1(t) = s$. Then $phi|_S-s$ maps $S-s$ to $T-t$, and by the induction hypothesis this map can't be one-to-one. So in all cases $phi$ fails to be one-to-one.






share|cite|improve this answer






















  • Sorry, because of short of knowledge of math, I cannot understand completely, But anyway, thank you very much for your help.
    – An Yan
    13 hours ago







  • 2




    While I'm sorry to be critical of this post, it is disappointing to me that the most upvoted answer (at this time) is one that gets an "A" grade in how to do math, but only gets a "D" grade in how to explain math to others. Know your audience and keep it simple are key principles in teaching.
    – Paul Sinclair
    8 hours ago






  • 10




    @PaulSinclair It's really because OP was confusing - the title and body of the question are different. The question in the body - answered by the accepted answer - is "How do I apply the pigeonhole principle", while the question in the title - answered here - is "How do I prove the pigeonhole principle". These not only necessitate different answers, but also imply different audiences. While the other answer works for OP, it would be a disappointment to anyone who found the question by title alone if it didn't have this answer.
    – Ordous
    7 hours ago










  • @Ordous Thank you.
    – John Brevik
    5 hours ago






  • 1




    @PaulSinclair I thought the OP was looking for a proof of the Pigeonhole Principle. I don't see why you needed to take a swipe at me for trying to help.
    – John Brevik
    5 hours ago














up vote
18
down vote













The Pigeonhole Principle is really the statement that for finite sets $S,T$ with $|S|>|T|$, there is no injective mapping from $S$ to $T$. Proceed by induction on $|T|$. For $|T|=1$, $|S|ge 2$ by hypothesis; there is one map from $S$ to $T$ and it is not one-to-one. Now suppose true for sets with $n$ elements and that $|T|=n+1$ (and $|S|>n+1$), and let $phi:Sto T$. Let $tin T$. Then as there are no injective mappings from $S$ to $T-t$ by the induction hypothesis, $phi$ won't be injective unless some $sin S$ maps to $t$, so suppose this is so. If another element also maps to $T$, then clearly $phi$ is not one-to-one, so suppose that $phi^-1(t) = s$. Then $phi|_S-s$ maps $S-s$ to $T-t$, and by the induction hypothesis this map can't be one-to-one. So in all cases $phi$ fails to be one-to-one.






share|cite|improve this answer






















  • Sorry, because of short of knowledge of math, I cannot understand completely, But anyway, thank you very much for your help.
    – An Yan
    13 hours ago







  • 2




    While I'm sorry to be critical of this post, it is disappointing to me that the most upvoted answer (at this time) is one that gets an "A" grade in how to do math, but only gets a "D" grade in how to explain math to others. Know your audience and keep it simple are key principles in teaching.
    – Paul Sinclair
    8 hours ago






  • 10




    @PaulSinclair It's really because OP was confusing - the title and body of the question are different. The question in the body - answered by the accepted answer - is "How do I apply the pigeonhole principle", while the question in the title - answered here - is "How do I prove the pigeonhole principle". These not only necessitate different answers, but also imply different audiences. While the other answer works for OP, it would be a disappointment to anyone who found the question by title alone if it didn't have this answer.
    – Ordous
    7 hours ago










  • @Ordous Thank you.
    – John Brevik
    5 hours ago






  • 1




    @PaulSinclair I thought the OP was looking for a proof of the Pigeonhole Principle. I don't see why you needed to take a swipe at me for trying to help.
    – John Brevik
    5 hours ago












up vote
18
down vote










up vote
18
down vote









The Pigeonhole Principle is really the statement that for finite sets $S,T$ with $|S|>|T|$, there is no injective mapping from $S$ to $T$. Proceed by induction on $|T|$. For $|T|=1$, $|S|ge 2$ by hypothesis; there is one map from $S$ to $T$ and it is not one-to-one. Now suppose true for sets with $n$ elements and that $|T|=n+1$ (and $|S|>n+1$), and let $phi:Sto T$. Let $tin T$. Then as there are no injective mappings from $S$ to $T-t$ by the induction hypothesis, $phi$ won't be injective unless some $sin S$ maps to $t$, so suppose this is so. If another element also maps to $T$, then clearly $phi$ is not one-to-one, so suppose that $phi^-1(t) = s$. Then $phi|_S-s$ maps $S-s$ to $T-t$, and by the induction hypothesis this map can't be one-to-one. So in all cases $phi$ fails to be one-to-one.






share|cite|improve this answer














The Pigeonhole Principle is really the statement that for finite sets $S,T$ with $|S|>|T|$, there is no injective mapping from $S$ to $T$. Proceed by induction on $|T|$. For $|T|=1$, $|S|ge 2$ by hypothesis; there is one map from $S$ to $T$ and it is not one-to-one. Now suppose true for sets with $n$ elements and that $|T|=n+1$ (and $|S|>n+1$), and let $phi:Sto T$. Let $tin T$. Then as there are no injective mappings from $S$ to $T-t$ by the induction hypothesis, $phi$ won't be injective unless some $sin S$ maps to $t$, so suppose this is so. If another element also maps to $T$, then clearly $phi$ is not one-to-one, so suppose that $phi^-1(t) = s$. Then $phi|_S-s$ maps $S-s$ to $T-t$, and by the induction hypothesis this map can't be one-to-one. So in all cases $phi$ fails to be one-to-one.







share|cite|improve this answer














share|cite|improve this answer



share|cite|improve this answer








edited 9 hours ago

























answered 13 hours ago









John Brevik

1,51049




1,51049











  • Sorry, because of short of knowledge of math, I cannot understand completely, But anyway, thank you very much for your help.
    – An Yan
    13 hours ago







  • 2




    While I'm sorry to be critical of this post, it is disappointing to me that the most upvoted answer (at this time) is one that gets an "A" grade in how to do math, but only gets a "D" grade in how to explain math to others. Know your audience and keep it simple are key principles in teaching.
    – Paul Sinclair
    8 hours ago






  • 10




    @PaulSinclair It's really because OP was confusing - the title and body of the question are different. The question in the body - answered by the accepted answer - is "How do I apply the pigeonhole principle", while the question in the title - answered here - is "How do I prove the pigeonhole principle". These not only necessitate different answers, but also imply different audiences. While the other answer works for OP, it would be a disappointment to anyone who found the question by title alone if it didn't have this answer.
    – Ordous
    7 hours ago










  • @Ordous Thank you.
    – John Brevik
    5 hours ago






  • 1




    @PaulSinclair I thought the OP was looking for a proof of the Pigeonhole Principle. I don't see why you needed to take a swipe at me for trying to help.
    – John Brevik
    5 hours ago
















  • Sorry, because of short of knowledge of math, I cannot understand completely, But anyway, thank you very much for your help.
    – An Yan
    13 hours ago







  • 2




    While I'm sorry to be critical of this post, it is disappointing to me that the most upvoted answer (at this time) is one that gets an "A" grade in how to do math, but only gets a "D" grade in how to explain math to others. Know your audience and keep it simple are key principles in teaching.
    – Paul Sinclair
    8 hours ago






  • 10




    @PaulSinclair It's really because OP was confusing - the title and body of the question are different. The question in the body - answered by the accepted answer - is "How do I apply the pigeonhole principle", while the question in the title - answered here - is "How do I prove the pigeonhole principle". These not only necessitate different answers, but also imply different audiences. While the other answer works for OP, it would be a disappointment to anyone who found the question by title alone if it didn't have this answer.
    – Ordous
    7 hours ago










  • @Ordous Thank you.
    – John Brevik
    5 hours ago






  • 1




    @PaulSinclair I thought the OP was looking for a proof of the Pigeonhole Principle. I don't see why you needed to take a swipe at me for trying to help.
    – John Brevik
    5 hours ago















Sorry, because of short of knowledge of math, I cannot understand completely, But anyway, thank you very much for your help.
– An Yan
13 hours ago





Sorry, because of short of knowledge of math, I cannot understand completely, But anyway, thank you very much for your help.
– An Yan
13 hours ago





2




2




While I'm sorry to be critical of this post, it is disappointing to me that the most upvoted answer (at this time) is one that gets an "A" grade in how to do math, but only gets a "D" grade in how to explain math to others. Know your audience and keep it simple are key principles in teaching.
– Paul Sinclair
8 hours ago




While I'm sorry to be critical of this post, it is disappointing to me that the most upvoted answer (at this time) is one that gets an "A" grade in how to do math, but only gets a "D" grade in how to explain math to others. Know your audience and keep it simple are key principles in teaching.
– Paul Sinclair
8 hours ago




10




10




@PaulSinclair It's really because OP was confusing - the title and body of the question are different. The question in the body - answered by the accepted answer - is "How do I apply the pigeonhole principle", while the question in the title - answered here - is "How do I prove the pigeonhole principle". These not only necessitate different answers, but also imply different audiences. While the other answer works for OP, it would be a disappointment to anyone who found the question by title alone if it didn't have this answer.
– Ordous
7 hours ago




@PaulSinclair It's really because OP was confusing - the title and body of the question are different. The question in the body - answered by the accepted answer - is "How do I apply the pigeonhole principle", while the question in the title - answered here - is "How do I prove the pigeonhole principle". These not only necessitate different answers, but also imply different audiences. While the other answer works for OP, it would be a disappointment to anyone who found the question by title alone if it didn't have this answer.
– Ordous
7 hours ago












@Ordous Thank you.
– John Brevik
5 hours ago




@Ordous Thank you.
– John Brevik
5 hours ago




1




1




@PaulSinclair I thought the OP was looking for a proof of the Pigeonhole Principle. I don't see why you needed to take a swipe at me for trying to help.
– John Brevik
5 hours ago




@PaulSinclair I thought the OP was looking for a proof of the Pigeonhole Principle. I don't see why you needed to take a swipe at me for trying to help.
– John Brevik
5 hours ago










up vote
3
down vote













I don't like quoting the pigeonhole principle when it is nothing more than common sense. Like this:




There are only $19$ possible two-digit sums, because the smallest is $0+0$ and the largest is $9+9$ and there are only $19$ integers from $0$ to $18$. So obviously if you have $20$ two-digit numbers, they cannot all have different digit sums, because $20 > 19$.




More generally, if you have $c·k+1$ items and assign one of $c$ labels to each item, there is a label assigned to at least $k+1$ items. Proof: If the claim is false, then every label is assigned to at most $k$ items, so there can be at most $c·k$ items, contradicting the given number of items. Therefore the claim is true.






share|cite|improve this answer




















  • Of course, translating this 'common sense' into formal rigorous reasoning is possible (such as in higher-order arithmetic or ZFC set theory), but it is not instructive at this level, because the intrinsic reasoning will be obscured.
    – user21820
    11 hours ago














up vote
3
down vote













I don't like quoting the pigeonhole principle when it is nothing more than common sense. Like this:




There are only $19$ possible two-digit sums, because the smallest is $0+0$ and the largest is $9+9$ and there are only $19$ integers from $0$ to $18$. So obviously if you have $20$ two-digit numbers, they cannot all have different digit sums, because $20 > 19$.




More generally, if you have $c·k+1$ items and assign one of $c$ labels to each item, there is a label assigned to at least $k+1$ items. Proof: If the claim is false, then every label is assigned to at most $k$ items, so there can be at most $c·k$ items, contradicting the given number of items. Therefore the claim is true.






share|cite|improve this answer




















  • Of course, translating this 'common sense' into formal rigorous reasoning is possible (such as in higher-order arithmetic or ZFC set theory), but it is not instructive at this level, because the intrinsic reasoning will be obscured.
    – user21820
    11 hours ago












up vote
3
down vote










up vote
3
down vote









I don't like quoting the pigeonhole principle when it is nothing more than common sense. Like this:




There are only $19$ possible two-digit sums, because the smallest is $0+0$ and the largest is $9+9$ and there are only $19$ integers from $0$ to $18$. So obviously if you have $20$ two-digit numbers, they cannot all have different digit sums, because $20 > 19$.




More generally, if you have $c·k+1$ items and assign one of $c$ labels to each item, there is a label assigned to at least $k+1$ items. Proof: If the claim is false, then every label is assigned to at most $k$ items, so there can be at most $c·k$ items, contradicting the given number of items. Therefore the claim is true.






share|cite|improve this answer












I don't like quoting the pigeonhole principle when it is nothing more than common sense. Like this:




There are only $19$ possible two-digit sums, because the smallest is $0+0$ and the largest is $9+9$ and there are only $19$ integers from $0$ to $18$. So obviously if you have $20$ two-digit numbers, they cannot all have different digit sums, because $20 > 19$.




More generally, if you have $c·k+1$ items and assign one of $c$ labels to each item, there is a label assigned to at least $k+1$ items. Proof: If the claim is false, then every label is assigned to at most $k$ items, so there can be at most $c·k$ items, contradicting the given number of items. Therefore the claim is true.







share|cite|improve this answer












share|cite|improve this answer



share|cite|improve this answer










answered 11 hours ago









user21820

37k441144




37k441144











  • Of course, translating this 'common sense' into formal rigorous reasoning is possible (such as in higher-order arithmetic or ZFC set theory), but it is not instructive at this level, because the intrinsic reasoning will be obscured.
    – user21820
    11 hours ago
















  • Of course, translating this 'common sense' into formal rigorous reasoning is possible (such as in higher-order arithmetic or ZFC set theory), but it is not instructive at this level, because the intrinsic reasoning will be obscured.
    – user21820
    11 hours ago















Of course, translating this 'common sense' into formal rigorous reasoning is possible (such as in higher-order arithmetic or ZFC set theory), but it is not instructive at this level, because the intrinsic reasoning will be obscured.
– user21820
11 hours ago




Of course, translating this 'common sense' into formal rigorous reasoning is possible (such as in higher-order arithmetic or ZFC set theory), but it is not instructive at this level, because the intrinsic reasoning will be obscured.
– user21820
11 hours ago

















 

draft saved


draft discarded















































 


draft saved


draft discarded














StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2949860%2fa-standard-and-rigorous-proof-using-the-pigeonhole-principle%23new-answer', 'question_page');

);

Post as a guest













































































Popular posts from this blog

How to check contact read email or not when send email to Individual?

Displaying single band from multi-band raster using QGIS

How many registers does an x86_64 CPU actually have?