1

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!

Erik Vesterlund
  • 1,526
  • Are you sure you have written the question down correctly? Because as it stands the answer is obviously wrong, and in fact makes no sense. – Alex Becker Aug 20 '13 at 05:33
  • @AlexBecker Double checked, and yes it's correct, it may be my translation that's incorrect though. I'll try to think of a different formulation. – Erik Vesterlund Aug 20 '13 at 05:36

1 Answers1

3

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\}$.

Brian M. Scott
  • 616,228
  • Hm, what kind of object is ${,\bar f:f\in M,}$ here? A set as the notation suggests? Then no two members of it are equal ... Preferably maybe: the map $f\mapsto \bar f$ cannot be injective. – Hagen von Eitzen Aug 20 '13 at 06:27
  • @Hagen: It’s a relic that I thought that I’d removed before posting. It’s gone now. – Brian M. Scott Aug 20 '13 at 06:36