Mixing
A standard and rigorous proof using the pigeonhole principle
Clash Royale CLAN TAG#URR8PPP
up vote
5
down vote
favorite
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
edited 9 mins ago
Ari Brodsky
302211
asked 14 hours ago
An Yan
435
add a comment |Â
up vote
5
down vote
favorite
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
edited 9 mins ago
Ari Brodsky
302211
asked 14 hours ago
An Yan
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
add a comment |Â
up vote
5
down vote
favorite
up vote
5
down vote
favorite
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
edited 9 mins ago
Ari Brodsky
302211
asked 14 hours ago
An Yan
435
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
combinatorics pigeonhole-principle
edited 9 mins ago
Ari Brodsky
302211
asked 14 hours ago
An Yan
435
edited 9 mins ago
Ari Brodsky
302211
asked 14 hours ago
An Yan
435
edited 9 mins ago
Ari Brodsky
302211
edited 9 mins ago
Ari Brodsky
302211
edited 9 mins ago
Ari Brodsky
302211
302211
asked 14 hours ago
An Yan
435
asked 14 hours ago
An Yan
435
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
add a comment |Â
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
add a comment |Â
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.
answered 14 hours ago
Wuestenfux
1,577139
The application of the principle accomplishes the proof.
– Wuestenfux
14 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
add a comment |Â
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.
answered 13 hours ago
John Brevik
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
 |Â
show 2 more comments
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.
answered 11 hours ago
user21820
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
add a comment |Â
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.
answered 14 hours ago
Wuestenfux
1,577139
The application of the principle accomplishes the proof.
– Wuestenfux
14 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
add a comment |Â
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.
answered 14 hours ago
Wuestenfux
1,577139
The application of the principle accomplishes the proof.
– Wuestenfux
14 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
add a comment |Â
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.
answered 14 hours ago
Wuestenfux
1,577139
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.
answered 14 hours ago
Wuestenfux
1,577139
edited 13 hours ago
answered 14 hours ago
Wuestenfux
1,577139
answered 14 hours ago
Wuestenfux
1,577139
answered 14 hours ago
Wuestenfux
1,577139
1,577139
The application of the principle accomplishes the proof.
– Wuestenfux
14 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
add a comment |Â
The application of the principle accomplishes the proof.
– Wuestenfux
14 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
14 hours ago
The application of the principle accomplishes the proof.
– Wuestenfux
14 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
add a comment |Â
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.
answered 13 hours ago
John Brevik
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
 |Â
show 2 more comments
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.
answered 13 hours ago
John Brevik
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
 |Â
show 2 more comments
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.
answered 13 hours ago
John Brevik
1,51049
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.
answered 13 hours ago
John Brevik
1,51049
edited 10 hours ago
answered 13 hours ago
John Brevik
1,51049
answered 13 hours ago
John Brevik
1,51049
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
 |Â
show 2 more comments
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
 |Â
show 2 more comments
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.
answered 11 hours ago
user21820
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
add a comment |Â
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.
answered 11 hours ago
user21820
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
add a comment |Â
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.
answered 11 hours ago
user21820
37k441144
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.
answered 11 hours ago
user21820
37k441144
answered 11 hours ago
user21820
37k441144
answered 11 hours ago
user21820
37k441144
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
add a comment |Â
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
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
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
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
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
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
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