A standard and rigorous proof using the pigeonhole principle

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?

Answer 1

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.

Answer 2

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.

Answer 3

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.