> [!NOTE] Proposition (Pigeonhole Principle 1) > For every pair of *non-empty* [[Finite Set|finite sets]] $A$ and $B$ and for every [[Function|function]] $f:A\to B$, if $|A|>|B|$, then there exists an element $b\in B$ such that $|f^{-1}(b)\geq 2|$ (*i.e the are at least to members of $A$ whose [[Image of a set under a function|image]] is $b$*). ^6a4b80 >*Proof*. BWOC, suppose for all $b\in B$, $|f^{-1}(b)|\leq1$. Note that $|A| = \sum_{b\in B} |f^{-1}(b)| \leq|B|$which contradicts the fact that $|A|>|B|$. $\square$ > >Note that this shows that $f$ cannot be [[Injection|injective]]. >*Proof*. Use *pigeonhole principle 2* with $c=1$. >*Proof*. Using *pigeonhole principle 3* with $q_{i}=2$ for $i\in[n]$. > [!NOTE] Proposition (Pigeonhole Principle 2) > For every pair of non-empty *finite sets* $A$ and $B$ and for every *function* $f:A\to B$, if $\exists c\in \mathbb{N}$ such that $|A|>c|B|$, then there exists an element $b\in B$ such that $|f^{-1}(b)| \geq c+1.$ ^d018fb >*Proof*. BWOC, suppose for all $b\in B$, $|f^{-1}(b)|\leq c$. Note that $|A| = \sum_{b\in B} |f^{-1} (b)| \leq c|B|$which contradicts the fact that $|A|>c|B|$. $\square$ >*Proof*. Use *pigeonhole principle 3* with $q_{i}=c$ for $i\in[n]$. > [!NOTE] Proposition (Pigeonhole Principle 3) >Let $q_{1},\dots,q_{n}\in\mathbb{N}$. For every pair of non-empty *finite sets* $A=\{ a_{1},\dots,a_{r} \}$ and $B=\{ b_{1},\dots,b_{n} \}$ such that $r= \left( \sum_{i\in[n]} q_{i} \right) - n + 1,$and for every function $f:A\to B$ , there exists $i\in [{n}]$ such that $|f^{-1}(b_{i})|\geq q_{i}$. *(Note that $[n]=\{ 1,\dots,n \}$)*. > >Equivalently, If $q_{1}+\dots+q_{n}+n-1$ objects are put into $n$ boxes then either the $1$st box contains at least $q_{1}$ objects, or the $2$nd box contains at least $q_{2}$ objects, ..., the $n$th box contains at least $q_{n}$ objects. >*Proof*. Suppose to the contrary that for some $q_{1},\dots,q_{n}\in\mathbb{N}$ and pair of sets $A=\{ a_{1},\dots,a_{r} \}$ and $B=\{ b_{1},\dots,b_{n} \}$ such that $r=\left( \sum_{i\in[n]} q_{i}\right)-n+1$ and some function $f:A\to B$, for all $i\in[n]$, $|f^{-1}(b_{i})|\leq q_{i}-1$. Then we have the following contradiction to the size of $A$ $|A|=\sum_{i\in[n]} |f^{-1}(b_{i})| \leq \sum_{i\in[n]} (q_{i} -1) =\left( \sum_{i\in[n]} q_{i} \right) -n <r .$ # Applications ###### Examples: - [[Any set of 101 positive integers that are at most 200 contains factor-multiple pair]]. > [!Example] > Show that for any $n+1$ integers $\{ a_{1},\dots,a_{n+1} \}$, there must exist $a_{i}$ and $a_{j}$ $(i\neq j)$ such that $n$ divides $a_{i}-a_{j}$. > >**Solution**. Define $\begin{align} f: \{ a_{1},\dots,a_{n+1} \} & \to \mathbb{Z}/n\mathbb{Z} \\ x &\mapsto [x]_{n} \end{align}$Note that $|\mathbb{Z}/n\mathbb{Z}|=n$ and $|\{ a_{1},\dots,a_{n+1} \}|=n+1$. By pigeonhole principle, there are two numbers congruent $\pmod{n}$. > [!Example] > Show that for any integers $\{ a_{1},\dots,a_{n} \}$, there exists integers $k$ and $l$ with $1\leq k\leq l \leq n$ such that $n$ divides $a_{k}+a_{k+1}+a_{k+2}+\dots+a_{l}$. > > **Solution**. Consider the the following sums $a_{1},a_{1}+a_{2},\dots,a_{1}+\dots+a_{n}$ modulo $n.$ > > Case 1 : At least one of these are congruent to $0 \pmod{n}$ then we are done. > > Case 2: Otherwise, there at most $n-1$ possible remainders modulo $n$ and by pigeonhole principle, there must exist $k<l$ such that $a_{1}+\dots+a_{k} \equiv a_{1}+\dots +a_{l} \pmod{n}.$ Therefore for $n$ divides the difference $a_{k+1}+a_{k+2}\dots+ a_{l}.$ > [!Example] Example > Show that if $A$ is a set of $10$ numbers from the set $\{ 1,\dots,80 \}$, then there are two distinct disjoint subsets of $A$ whose elements sum to the same number. > > **Solution**. There are $2^{10}-1=1023$ non empty subsets of $A.$ The largest possible sum of the elements of $A$ is $80+\dots+71<1000.$ Hence, by the pigeonhole principle, there exists non-empty sets $A_{1},A_{2}\subseteq A$ such that the sum of $A_{1}$ equals the sum of $A_{2}.$ This also implies that between $A_{1}$ and $A_{2}$, neither can be a proper subset of the other. Removing thei intersection gives the solution. # Applications - [[Chinese remainder theorem]]. - [[Two vertices have the same degree]]. - [[Erdös-Szekeres Theorem]]. - Useful in proving that as set system has as an [[System of Distinct Representatives|SDR]].