Question

Show that if \(f\) is a function from \(S\) to \(T\), where \(S\) and \(T\) are nonempty finite sets and \(m = [|S|/|T|]\), then there are at least \(m\) elements of \(S\) mapped to the same value of \(T\). That is, show that there are distinct elements \({s_1},{s_2}, \ldots ,{s_m}\) of \(S\) such that \(f\left( {{s_1}} \right) = f\left( {{s_2}} \right) = \cdots = f\left( {{s_m}} \right)\).

Short answer

The resultant answer is that there is (at least) one value of \(T\) that can be mapped with \(m = \left\lceil {\frac{{|S|}}{{|T|}}} \right\rceil \) different elements of \(S\).

Step-by-step solution

Given data

The given function is \(m = [|S|/|T|]\).

Concept of Pigeonhole principle

If the number of pigeons exceeds the number of pigeonholes, at least one hole will hold at least two pigeons, according to the pigeon hole principle.

Simplify the expression

For the function \(f\), we are basically assigning different values of \(T\)to different members of \(S\). Here one can visualize the members of \(S\) as objects while the elements of \(T\) can be thought of as boxes. Two objects can be put into the same box but one object cannot be placed into two different boxes at the same time.

Using the generalized Pigeonhole Principle we can say that at least one box contains at least \(\left\lceil {\frac{{|S|}}{{|T|}}} \right\rceil \) objects, i.e. there is (at least) one value of \(T\) that can be mapped with \(m = \left\lceil {\frac{{|S|}}{{|T|}}} \right\rceil \) different elements of \(S\).