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?

  • 1
    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 Oct 10 at 11:26
  • 1
    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/d\rceil$ elements, assume otherwise then prove a contradiction. – YiFan Oct 10 at 11:28
  • @MarkBennet Ok, My expression is not very rigorous. My example is the most extreme one. – An Yan Oct 10 at 11:31
  • I don't think "00" counts as a two-digit number. So there are really only 18 possibilities. – Wildcard Oct 10 at 20:03
  • "I don't know the standard and rigorous proof of this problem." Have you googled it already? See for example: whitman.edu/mathematics/cgt_online/book/section01.06.html for a very simple proof, second result on google. – Trilarion Oct 11 at 11:53
up vote 17 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.

  • The application of the principle accomplishes the proof. – Wuestenfux Oct 10 at 11:24
  • 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 Oct 10 at 11:36
  • Right. This is the case. – Wuestenfux Oct 10 at 11:37
  • OK, I see, thank you very much – An Yan Oct 10 at 11:40

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:S\to T$. Let $t\in T$. Then as there are no injective mappings from $S$ to $T-\{t\}$ by the induction hypothesis, $\phi$ won't be injective unless some $s\in 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.

  • 1
    Sorry, because of short of knowledge of math, I cannot understand completely, But anyway, thank you very much for your help. – An Yan Oct 10 at 11:34
  • 6
    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 Oct 10 at 16:29
  • 15
    @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 Oct 10 at 17:54
  • 2
    @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 Oct 10 at 19:39
  • 1
    @JohnBrevik - It was not a swipe at you. I meant it when I said I'm sorry to criticize. But it is an honest critique of the appropriateness of your answer, and I will not apologize for that. This is something you need to improve on if you wish to be helpful. My disappointment is not with your answer, but with the failure of so many others to recognize that it wasn't helpful to the OP because you didn't take the OP's level of sophistication into consideration. – Paul Sinclair Oct 10 at 23:39

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.

  • 1
    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 Oct 10 at 14:09
  • 2
    The pigeonhole principle is not at all a surprising result, but I think it has a name more because it's a useful category of thinking about how to solve problems, when it might not be obvious it does apply. "I need to show some subset of a finite set has something in common - can I sort all the elements into some list of possible categories?" – aschepler Oct 11 at 3:37
  • @aschepler: That may be so, but my point was that it is pedagogically unwise to give names to lemmas that not only are trivially provable via simple logical reasoning but also obscure that reasoning when used directly. In this case, the "pigeonhole" name also carries with it some baggage that does not contribute to the mathematical pedagogy, since thinking in terms of "pigeons" and "holes" is less general than the idea of counting and bounding. For example getting the optimal bound for this question. – user21820 Oct 11 at 6:09

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.