Consider the set of all functions \(f:\{0,1, \dots,2014\} \to \{0,1,\dots,…
2014
Consider 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:
\(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
Attempted by 132 students.
Show answer & explanation
Correct answer: B
Answer: Only the statements that there exists some i with f(i)=i and that f is onto are true; the claim that every element must be fixed is false.
Why f is onto:
If f(a)=f(b) then applying f gives a=f(f(a))=f(f(b))=b, so f is injective. An injective map from a finite set to itself is bijective, hence onto.
Why there exists a fixed point:
The condition f(f(i))=i means every element belongs to either a 1-cycle (f(i)=i) or a 2-cycle (a pair swapped). The domain has 2015 elements, an odd number, so it cannot be partitioned entirely into 2-cycles (which use an even number of elements). Therefore at least one 1-cycle (fixed point) must exist.
Why not every element must be fixed:
There are involutions with 2-cycles. For example, define f(0)=1, f(1)=0, and f(i)=i for all other i. This satisfies f(f(i))=i but not every element is fixed, so the universal fixed-point claim is false.
A video solution is available for this question — log in and enroll to watch it.