GATE CS 2014 Set 3 Q49 — Sets, Relations and Functions

Let $S = \{0, 1, \dots, 2014\}$. The size of the set is $|S| = 2015$, which is an odd number. We are given that $f(f(i)) = i$ for all $i \in S$. This means $f$ is an involution (its own inverse).

• Statement $P$ is false: We can easily construct a function where not all elements are fixed. For example, let $f(0) = 1$, $f(1) = 0$, and $f(i) = i$ for all $i \geq 2$. This satisfies $f(f(i)) = i$, but $f(0) \neq 0$.
• Statement $Q$ is true: Since $f(f(i)) = i$, the elements of $S$ are partitioned into orbits of size 1 (fixed points where $f(i) = i$) and size 2 (pairs where $f(i) = j$ and $f(j) = i$ for $i \neq j$). If there are $k$ pairs of size 2 and $m$ fixed points, then:
  $$2k + m = 2015$$
  Since $2015$ is odd, $m$ must be odd and cannot be $0$. Thus, there is at least one fixed point ($f(i) = i$ for some $i$).
• Statement $R$ is true: Since $f(f(i)) = i$, the function $f$ has a two-sided inverse (itself). Any function with an inverse is a bijection, which means it must be onto.

Therefore, only $Q$ and $R$ are true.