I'm doing some exercises in proof-by-induction, and came across one where I need to prove both the Pigeonhole and the Extended Pigeonhole Principles. I've proved the former, and now I'm working to prove the latter, but I'm a little bit.
The Extended Pigeonhole Principle:
For any finite sets $X$ and $Y$ and any positive integer $|X| > k \cdot |Y|$, if $f: X \rightarrow Y$, then there are at least $k + 1$ distinct members $x_1, \dots, x_{k + 1} \in X$ such that $f(x) = \dots = f(x_{k+1})$.
My approach was to use $k$ as the induction variable, and basically to say whenever this is true for $k$, you can extend $X$ with $|Y|$ new elements, arbitrarily mapping them to elements in $Y$, and show that the principle must be true for $k + 1$. I've already proven the (Non-extended) Pigeonhole Principle, so where my proof makes use of it, I think that is considered OK.
My proof:
Clearly the Otherwise section is bogus and incomplete. As you can see, I'm trying to show that if the maximum cardinality of all $s \in S$ is $k + 1$, then no matter how you you add $|Y|$ new elements to these subsets, in the end you'll end up with at least one $s \in S$ such that $|s| = k + 2.
I can see this practically, e.g., consider $|X| = 11 and |Y| = 5$, such that $|X| > 2 \cdot |Y|$. Consider the sets $S$ and $A$, as mentioned in the proof. If you listed out the cardinalities of the sets in $S$, some possibilities are:
- $\{\{x_1, \dots, x_{k + 1}\}, \{x_1, \dots, x_k\}, \{x_1, \dots, x_k\}, \{x_1, \dots, x_k\}, \{x_1, \dots, x_k\}\}$
- $\{\{x_1, \dots, x_{k + 1}\}, \{x_1, \dots, x_{k + 1}\}, \{x_1, \dots, x_k\}, \{x_1, \dots, x_k\}, \{x_1, \dots, x_{k - 1}\}\}$
- $\{\{x_1, \dots, x_{k + 1}\}, \{x_1, \dots, x_{k + 1}\}, \{x_1, \dots, x_{k + 1}\}, \{x_1, \dots, x_k\}, \{x_1, \dots, x_{k - 2}\}\}$
- $\{\{x_1, \dots, x_{k + 1}\}, \{x_1, \dots, x_{k + 1}\}, \{x_1, \dots, x_{k + 1}\}, \{x_1, \dots, x_{k + 1}\}, \{x_1, \dots, x_{k - 3}\}\}$
Now take any one of the sets above, and consider dispersing $5$ new elements amongst any of its subsets. I'm trying to show that:
- If you add an an element to a set that already has $k + 1$ elements, of course the new cardinality will be $k + 2$, and the proof is done
- However if you avoid touching all sets with cardinalities $k + 1$, then you'll add enough elements to the other sets such that one will end up with $k + 2$ elements.
Any ideas how I can formally prove this?
The simplest approach is to prove the contrapositive: if $|\{x\in X:f(x)=y\}|\le k$ for each $y\in Y$, then $|X|\le k|Y|$. This is immediate, since then
$$|X|\le\sum_{y\in Y}|\{x\in X:f(x)=y\}\le k|Y|\;.$$
Added: There is no good reason to prove the result by induction, and I think it poor pædagogy to require such a proof, but since that seems to be desired, here is one possibility that actually uses the induction hypothesis directly.
The base case is just the pigeonhole principle, which we are assuming. Now take as induction hypothesis the assertion that if $X$ and $Y$ are any finite sets such that $|X|>k|Y|$, and $f:X\to Y$ is any function from $X$ to $Y$, then there are at least $k+1$ distinct $x_1,\ldots,x_{k+1}\in X$ such that $f(x_1)=\ldots=f(x_{k+1})$. Let $X$ and $Y$ be finite sets such that $|X|>(k+1)|Y|$, and let $f:X\to Y$ be a function.
Let $Y_0=\operatorname{ran}f=f[X]$, for each $y\in Y_0$ choose an $x_y\in X$ such that $f(x_y)=y$ and let $X_0=\{x_y:y\in Y_0\}$. Now let $X_1=X\setminus X_0$; clearly $|X_0|\le|Y|$, so $|X_1|>(k+1)|Y|-|Y_0|\ge k|Y|$, and by the induction hypothesis there are a $y\in Y$ and distinct $x_1,\ldots,x_{k+1}\in X_1$ such that $f(x_1)=\ldots=f(x_{k+1})=y$. But then $\{x_y,x_1,\ldots,x_{k+1}\}$ is a set of $k+2$ distinct members of $X$ such that $f(x_y)=f(x_1)=\ldots=f(x_{k+1})$, as desired, and by induction the result holds for all $k\in\Bbb Z^+$.