Mixing
The standard and rigorous proof of the pigeonhole principle
Clash Royale CLAN TAG#URR8PPP
up vote
2
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
asked 54 mins ago
An Yan
224
add a comment |Â
up vote
2
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
asked 54 mins ago
An Yan
224
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
40 mins 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
39 mins ago
@MarkBennet Ok, My expression is not very rigorous. My example is the most extreme one.
– An Yan
36 mins ago
add a comment |Â
up vote
2
down vote
favorite
up vote
2
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
asked 54 mins ago
An Yan
224
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
asked 54 mins ago
An Yan
224
asked 54 mins ago
An Yan
224
edited 25 mins ago
asked 54 mins ago
An Yan
224
asked 54 mins ago
An Yan
224
asked 54 mins ago
An Yan
224
224
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
40 mins 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
39 mins ago
@MarkBennet Ok, My expression is not very rigorous. My example is the most extreme one.
– An Yan
36 mins 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
40 mins 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
39 mins ago
@MarkBennet Ok, My expression is not very rigorous. My example is the most extreme one.
– An Yan
36 mins 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
40 mins 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
40 mins 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
39 mins 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
39 mins ago
@MarkBennet Ok, My expression is not very rigorous. My example is the most extreme one.
– An Yan
36 mins ago
@MarkBennet Ok, My expression is not very rigorous. My example is the most extreme one.
– An Yan
36 mins ago
add a comment |Â
2 Answers
2
active
oldest
votes
up vote
3
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 46 mins ago
Wuestenfux
1,497128
The application of the principle accomplishes the proof.
– Wuestenfux
42 mins 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
31 mins ago
Right. This is the case.
– Wuestenfux
29 mins ago
OK, I see, thank you very much
– An Yan
27 mins ago
add a comment |Â
up vote
3
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 36 mins ago
John Brevik
1,35248
Sorry, because of short of knowledge of math, I cannot understand completely, But anyway, thank you very much for your help.
– An Yan
33 mins ago
add a comment |Â
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
3
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 46 mins ago
Wuestenfux
1,497128
The application of the principle accomplishes the proof.
– Wuestenfux
42 mins 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
31 mins ago
Right. This is the case.
– Wuestenfux
29 mins ago
OK, I see, thank you very much
– An Yan
27 mins ago
add a comment |Â
up vote
3
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 46 mins ago
Wuestenfux
1,497128
The application of the principle accomplishes the proof.
– Wuestenfux
42 mins 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
31 mins ago
Right. This is the case.
– Wuestenfux
29 mins ago
OK, I see, thank you very much
– An Yan
27 mins ago
add a comment |Â
up vote
3
down vote
accepted
up vote
3
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 46 mins ago
Wuestenfux
1,497128
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 46 mins ago
Wuestenfux
1,497128
edited 3 mins ago
answered 46 mins ago
Wuestenfux
1,497128
answered 46 mins ago
Wuestenfux
1,497128
answered 46 mins ago
Wuestenfux
1,497128
1,497128
The application of the principle accomplishes the proof.
– Wuestenfux
42 mins 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
31 mins ago
Right. This is the case.
– Wuestenfux
29 mins ago
OK, I see, thank you very much
– An Yan
27 mins ago
add a comment |Â
The application of the principle accomplishes the proof.
– Wuestenfux
42 mins 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
31 mins ago
Right. This is the case.
– Wuestenfux
29 mins ago
OK, I see, thank you very much
– An Yan
27 mins ago
The application of the principle accomplishes the proof.
– Wuestenfux
42 mins ago
The application of the principle accomplishes the proof.
– Wuestenfux
42 mins 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
31 mins 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
31 mins ago
Right. This is the case.
– Wuestenfux
29 mins ago
Right. This is the case.
– Wuestenfux
29 mins ago
OK, I see, thank you very much
– An Yan
27 mins ago
OK, I see, thank you very much
– An Yan
27 mins ago
add a comment |Â
up vote
3
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 36 mins ago
John Brevik
1,35248
Sorry, because of short of knowledge of math, I cannot understand completely, But anyway, thank you very much for your help.
– An Yan
33 mins ago
add a comment |Â
up vote
3
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 36 mins ago
John Brevik
1,35248
Sorry, because of short of knowledge of math, I cannot understand completely, But anyway, thank you very much for your help.
– An Yan
33 mins ago
add a comment |Â
up vote
3
down vote
up vote
3
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 36 mins ago
John Brevik
1,35248
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 36 mins ago
John Brevik
1,35248
answered 36 mins ago
John Brevik
1,35248
answered 36 mins ago
John Brevik
1,35248
answered 36 mins ago
John Brevik
1,35248
1,35248
Sorry, because of short of knowledge of math, I cannot understand completely, But anyway, thank you very much for your help.
– An Yan
33 mins ago
add a comment |Â
Sorry, because of short of knowledge of math, I cannot understand completely, But anyway, thank you very much for your help.
– An Yan
33 mins ago
Sorry, because of short of knowledge of math, I cannot understand completely, But anyway, thank you very much for your help.
– An Yan
33 mins ago
Sorry, because of short of knowledge of math, I cannot understand completely, But anyway, thank you very much for your help.
– An Yan
33 mins 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%2fthe-standard-and-rigorous-proof-of-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
40 mins 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
39 mins ago
@MarkBennet Ok, My expression is not very rigorous. My example is the most extreme one.
– An Yan
36 mins ago