This is from an old exam:
Let $M$ be a set of functions from $\mathbb{Z}/3$ into itself. What is the least number of elements that $M$ must contain for there to surely be at least two elements $f,g \in M$ for which $f(0)=g(0)$ and $f(1)=g(1)$?
The solution goes like this:
Every function from $\mathbb{Z}/3$ into itself gives rise to a function $\bar{f}:\{0,1\} \rightarrow \mathbb{Z}/3$ by letting $\bar{f}(0)=f(0)$ and $\bar{f}(1)=f(1)$. For two functions to satisfy the conditions $f(0)=g(0)$ and $f(1)=g(1)$ it must hold that $\bar{f}=\bar{g}$. Then by the pigeonhole principle there must be at least ten functions in $M$ for these conditions to always hold.
Questions:
1) Why and how does $\bar{f}$ arise??
2) Why must the condition $\bar{f}=\bar{g}$ hold?
3) Why does the result follow from the pigeonhole principle?
I'm afraid I don't have anything of my own to contribute; in the associated literature the section (incl. exercises) regarding the pigeonhole principle does not mention a technique that looks similar to this. So, if anyone could explain the above solution further, provide alternative literature, or an alternative method of solving the problem, that'd be much appreciated, thanks!
The how of your first question is answered explicitly in the quoted solution: given a function $f:\Bbb Z/3\Bbb Z\to\Bbb Z/3\Bbb Z$, the associated function $\bar f:\{0,1\}\to\Bbb Z/3\Bbb Z$ is defined by $\bar f(0)=f(0)$ and $\bar f(1)=f(1)$. That definition tells precisely how $\bar f$ arises from $f$. The why is answered implicitly: $\bar f$ is a useful tool in proving that $|M|\ge 10$.
If $f(0)=g(0)$ and $f(1)=g(1)$, then by definition $\bar f(0)=f(0)=g(0)=\bar g(0)$ and $\bar f(1)=f(1)=g(1)=\bar g(1)$. And since $\{0,1\}$ is the entire domain of $\bar f$ and $\bar g$, we’ve just proved that if $f(0)=g(0)$ and $f(1)=g(1)$, then $\bar f=\bar g$: there is nothing in their common domain on which they could differ.
Since $\Bbb Z/3\Bbb Z$ has $3$ elements, there are $3$ possible choices for $\bar f(0)$ and $3$ possible choices for $\bar f(1)$. Thus, there are $3\cdot3=9$ different possible functions $\bar f$ from $\{0,1\}$ to $\Bbb Z/3\Bbb Z$. The pigeonhole principle then ensures that if you have more then $9$ functions from $\{0,1\}$ to $\Bbb Z/3\Bbb Z$, two of them must be the same function. In particular, if $|M|\ge 10$, then there must be distinct $f,g\in M$ such that $\bar f=\bar g$. If, on the other hand, $|M|$ is at most $9$, then we could have $\bar f\ne\bar g$ whenever $f,g\in M$ with $f\ne g$, and that would mean that no two members of $M$ agreed on $\{0,1\}$.