Consider the set of all functions f : {0,1,...,2014} -> {0,1,...,2014} such that f(f(i)) = i, for all 0 <= i <= 2014. Consider the following statements: P. For each such function it must be the case that for every i, f(i) = i. Q. For each such function it must be the case that for some i, f(i) = i. R. Each function must be onto. Which one of the following is CORRECT? A. P, Q and R are true B. Only Q and R are true C. Only P and Q are true D. Only R is true

GATE 2014 · Discrete Mathematics · Functions · medium

Answer: B. Only Q and R are true

1. f is a bijection, so R is true: Since applying f twice returns i, f is its own inverse, hence one-to-one and onto. So R (each function must be onto) is TRUE.
2. Refute P with a swap: This f satisfies f(f(i)) = i but f(0) = 1 != 0, so not every i is fixed. Hence P (every i has f(i) = i) is FALSE.
3. Prove Q from odd cardinality: An involution partitions the set into 2-cycles (swapped pairs) and fixed points. The set has 2015 elements (odd), and 2-cycles cover an even number of elements, so at least one element is left fixed. Hence Q (some i has f(i) = i) is TRUE.
4. Select the option: P is false, Q and R are true, which is 'Only Q and R are true', option B.