Pigeon Hole Theorem
Introduction
Pigeon Hole principle or sometimes known as the “Box Principal” is probably already something you are familiar with. You need $13$ people, in order to ensure a common birth month amongst them. The tricky part is identifying a pigeon hole problem. Similarly, figuring what are the pigeons and holes is not always obvious.
Definition
A pigeon is defined as the quantity of objects being counted, while holes are the groups they can be sorted into. The following are intuitive examples, to give you a feel before we move on to more challenging problems.
Theorem
For $Nk+1$ “pigeons in $N$ holes”, one of the holes will have at least $k+1$ “pigeons”, or in other words $\left\lceil\frac{nk+1}{h}\right\rceil$ which is read as “The ceiling of \(nk+1\) divided by $h$ rounded up to the nearest integer. For example $ \left\lceil\frac{1}{4}\right\rceil=1$ and $ \left\lceil\frac{\pi}{1}\right\rceil=4 $
$367$ people are needed to guarantee at least two people have a common birthday because there are $366$ days different days (in Gregorian calendars including leap years), so we need $n+1$ pigeons $(366+1)$ to guarantee at least $2$ people share one hole.
Mini Exercises
-
Show that amongst $N$ friends, there exists at least two people with same amount of friends.
Solution: The number of friends range from $0$ through $(N-1)$ friends (because you cannot be your own friend), which means there are $N$ choices for $N$ friends. If one person has zero friends, then it is impossible for another person to be friends with everyone. So there are $N-1$ holes amongst $N$ pigeons. $QED$
-
Five points are chosen in a $6$ by $6$ square. Show that two points are within a distance of $3\sqrt2$ units from other.
Solution: Assuming worst case scenario, we maximize the distance of the four points from each other. Using pythagorean theorem, the diagonal has length of
\[\\begin{align*} a^2+b^2 = \\ &c^2 \\ 6^2+6^2 = \\ &72 \\ = \\ &c^2 \\ &c = \\sqrt72 \\ &c = 6\\sqrt2 \\ \\end{align*}\]Which leaves us a fifth point to assign. The most equidistant location is the center of the square, or the midpoint of one the diagonals.
\[\\begin{align*} \\text{diaganol} &=6\\sqrt2 \\ \\text{midpoint} &=3\\sqrt2 \\ \\href{https://en.wikipedia.org/wiki/Q.E.D.}{QED} \\end{align*}\] -
Ten points inside a circle with a diameter of $5$. Prove that for any these ten points there exist two points whose distance is less than $2$.
Solution: After assigning 9 points on the radius equidistant from each other, as we did in previous exercise, we realize that if 10th point were in center it would be 2.5 units away from all the other points because a radius is half the diameter: $\frac{5}{2}=2.5$
We need to reduce the number of holes.
We add a concentric circle, with a radius of one. So any two points inside the circle would be within distance, in essence we reduced the number of holes from nine to eight. which is Dividing the larger circle into 8 congruent slices with equal radius Then the distances formulas show us the distance between any two points is $\le2$
\[\\begin{align*} &\\sqrt{1^{2} + \\left(\\frac{5}{2}\\right)^{2} - \\frac{5\\sqrt{2}}{2}} =\\ &\\sqrt{1 + \\frac{25}{4} - \\frac{5\\sqrt{2}}{2}} = \\ &\\sqrt{\\frac{29 - 10 \\sqrt{2}}{4}} < 2 \\ &\\text{QED} \\ \\end{align*}\]
Fibonacci challenge
The Fibonacci Sequence, $ 1, 1, 2, 3, 5, 8, 13, 21, 34, 55,\dots $ defined as $ F_{n}= F_{n-1} + F_{n-2}$ with seed values of $ F_{1}= F_{2} = 1 $
Consider the Fibonacci sequence $\pmod{10}$ which is $ 1, 1, 2, 3, 5, 8, 3, 1, 4, 5,\dots$
Show that there are infinitely many Fibonacci numbers ending in a zero i.e that there exists a $F_{n}$ which ends with $k$ zeroes.
In previous examples, we dealt with finite or bounded context (e.g countable objects or geometric areas). Here spotting that this is a pigeon hole problem is already significant.
Solution: A term $F_{p}$ ends in $k$ zeroes, if it is divisible by $10^{k}$. Consider the Fibonacci Sequence modulo $10^{k}$. Prove there exists some $P$ such that $F_{p} \equiv 0 \pmod{10^{k}}$. Consider the sequence of pairs $m_{0},m_{1},m_{2},\dots,m_{i}$ where $m_{0} = (M_{1},M_{2})$ $m_{1} = (M_{2},M_{3})$ where \(m_{i} = (F_{i} \\pmod{10^{k}}, F_{i+1} \\pmod{10^{k}})\) For modulo $10^{k}$ there are at most $(10^{k})^{2}$ or $10^{2k}$ possible residue pairs.
\[\\begin{align*} m_{0} &= (M_{0},M_{1}) \\ m_{1} &= (M_{1},M_{2}) \\ m_{n} &= (M_{n},M_{n+1}) \\ \\end{align*}\]We have at most $(10^{2k})$ distinct residue pairs $m_{0}, m_{1}, \dots, m_{10^{2k}}$ so $m_{10^{2k}+1}$ must be congruent to a previous term.
We have shown that two congruent residue pairs exist, but not necessarily $F_{p} \equiv 0 \pmod{10^{k}}$. Without loss of generality two distinct modular pairs $m_{k}, m_{g}$, their previous and successive terms are congruent. We can keep subtracting from both sides until they are congruent to $0 \pmod{10^{k}}$
\[\\begin{align*} m_{k} &\\equiv m_{g} \\ m_{k-1} &\\equiv m_{g-1} \\ m_{k-k} &\\equiv m_{g-k} \\ m_{0} &\\equiv m_{g-k} \\ 0 = m_{0} &\\equiv m_{g-k} \\ g &\\neq k \\ \\end{align*}\]