Question 59

Let $S = \{0, 1, \dots, 2014\}$. The size of $S$ is $|S| = 2014 - 0 + 1 = 2015$, which is an odd integer.
We are given $f(f(i)) = i$ for all $i \in S$, meaning $f \circ f = \text{id}_S$.

1. Statement R (Each such function must be onto):

   • Because $f \circ f = \text{id}_S$, $f$ has a two-sided inverse (namely $f$ itself).
   • Any function with a two-sided inverse is a bijection (both one-to-one and onto).
   • Hence, $f$ must be onto. Statement R is TRUE.

2. Statement P (For every $i$, $f(i) = i$):

   • Consider a function that swaps $0$ and $1$ ($f(0) = 1, f(1) = 0$) and fixes all other elements ($f(i) = i$ for all $i \ge 2$).
   • Here $f(f(i)) = i$ holds for all $i$, but $f(0) \ne 0$.
   • Thus, $f(i) = i$ is not required for every $i$. Statement P is FALSE.

3. Statement Q (For some $i$, $f(i) = i$):

   • In cycle notation, any permutation satisfying $f^2 = \text{id}$ can only contain cycles of length 1 (fixed points, $f(i) = i$) or length 2 (transpositions, $f(a) = b$ and $f(b) = a$).
   • Let $k$ be the number of fixed points, and $m$ be the number of 2-cycles.
   • The total number of elements in $S$ is:
     $$k + 2m = 2015.$$
   • Since $2m$ is even and $2015$ is odd, $k$ must be an odd integer ($k \ge 1$).
   • Hence, there must exist at least one fixed point ($f(i) = i$ for some $i$).
   • Therefore, Statement Q is TRUE.

4. Thus, only Q and R are true (option B).