Counting Insights Vol 1.1 Pigeon-Hole Principle

In Vol 1.0 of $k$-to-$1$ Functions, we considered the Devotee-Footwear problem, in which we asked: what is the minimum possible count of devotees present in the temple (exclude the priest)? Now a question arises that why there exists a minimum count (lower-bound) on the number of devotees? Can we prove mathematically the existence of such a lower-bound?

Theorem 1. Let $f:A\to B$ be $k$-to-$1$ function, and let $B$ be finite. Then, set $A$ is finite with size $\left|A\right| \le k\times \left|B\right|$.
Proof: Since $B$ is given to be finite, let $\left|B\right|=n$. Since $f()$ is $k$-to-$1$.
$\implies \left|f^{-1}(b)\right| \le k\ \forall b\in B$.
To show upper-bound on size of $A$, assume $f$ to be surjective.
$\implies \forall b \in B, \exists$ at most $k$ pre-images in $A$.
But $\left|B\right|=n. \implies \exists$ at most $k\times n$ elements in $A$.
Thus, $\left|A\right| \le k\times \left|B\right|$. $\space\blacksquare$

Note: $A$ achieves its maximum size only when $f$ is a surjection and every $b\in B$ has $k=\frac{\left|A\right|}{\left|B\right|}$ number of pre-images.

Let us now recall, $S$ = set of all footwears lying outside the temple entrance, and $D$ = set of all devotees present inside the temple, excluding the priest.
We defined actual mapping $g:S\to D$ that assignes each footwear to a unique devotee in $D$ and the map $g()$ is $2$-to-$1$. Now using Theorem 1, we have $\left|S\right| \le 2\times \left|D\right|$.
$\implies \left|D\right| \ge \frac{1}{2}\times \left|S\right|$.
Thus, for a given number of footwears (i.e., $\left|S\right|$), the number of devotees $\left|D\right|$ has a lower-bound $=\frac{1}{2}\times 112 = 56$, which is the required answer to “Devotee-Footwear” problem. Thus the count of devotees can vary from $56$ (minimum) to $112$ (maximum).

---

Contrapositive of Theorem $1$ is so effective in rejecting certain claims or proving certain guarantees, that we state it separately:
Theorem 1. (Contrapositive): Let sets $A$ and $B$ be such that $\left|A\right| > k\times \left|B\right|$, then there can not exist a $k$-to-$1$ map $f: A\to B$, i.e., $\exists\ b\in B$ such that $\left|f^{-1}(b)\right| > k$ (at least $\lceil\frac{\left|A\right|}{\left|B\right|}\rceil$ pre-images exist).

For example, suppose there are 56 devotees inside the temple (excluding the priest) and there are 113 footwears lying at the main entrance. Then clearly, $113 > 2\times 56$.
$\implies$ at least one devotee came to the temple with 3 pieces of footwears (Strange enough! but true).

Contrapositive of Theorem 1 is generally known as Dirichlet-Drawer Principle or Pigeon-Hole Principle. We have seen Theorem 1 being applicable to Devotee-Footwear example, but the theory developed in Theorem 1 is general enough to be applicable in diverse problems of same kind.
While encountering problems of this kind, identifying sets $A$ and $B$ correctly is quite often confusing. As a validation test, we can ask elements of which set can have multiple number of pre-images (including no premage, i.e., left unmapped). That set is the set $B$, which can have varying number of pre-images.

Written with StackEdit.