For the set of all functions $f:\{0,1, \dots,2014\} \to \{0,1,\dots, 2014\}$ such that $f\left(f\left(i\right)\right)=i$, for all $0 \leq i \leq 2014$.
Consider the following statements:
$A$ : For each such function it must be the case that for every $i,f(i) = i$
$B$ : For each such function it must be the case that for some $i,f(i) = i$
$C$ : Each function must be onto.
Which statements are correct, and why?
I tried this question using the same problem for a small set where $f:\{0,1\}\rightarrow\,\{0,1\}$.
It is found that statement $C$ always holds true and statement $A$ does not. I choose $B$ to be not true but in solution key it is marked true. Cannot understand the reason for that.
$\endgroup$ 71 Answer
$\begingroup$$A$ is false in general, consider the example: $$f(i) = \begin{cases} 1, & \text{if $i=0$} \\ 0, & \text{if $i=1$}\\ i,& \text{if $i>1$} \end{cases}$$
$C$ is true, clearly.
$B$ is also true, but this is more subtle. In particular it is true only because $2014$ is an even number. To see this, consider the pairing $(i,f(i))$ If there were no fixed points then each of those pairs consists of two elements. Clearly the pairs are disjoint and every element of $\{0,1,\dots, 2014\}$ is in exactly one of them. But that is absurd...there are $2015$ elements of the set and $2015$ is odd.
$\endgroup$
