GATE CSE 2014 Set 3 | Question: 49

Question

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

Comments

...

---

@GO Classes , @Deepak Poonia  Please sir explain 

---

@ayushjain321, See Detailed Solution here with Complete Analysis: https://gateoverflow.in/2083/gate-cse-2014-set-3-question-49?show=418152#a418152  

Answer 1

http://math.stackexchange.com/questions/1472091/composition-of-function-with-itself

Comments

Each function must be onto

Answer 2

Correct Answer - Option 2 : Only Q and R are true

Concept: Two functions f and g are inverse of each other if and only if f(g(x)) = g(f(x)) = x

 

Explanation: Using above property we can say that function f is inverse of itself this means,  

f(2)=3 then f(3)=2 but here total elements are 2015 so we can have total 1007 pair but one element is left for some element there exist  f(i) = i. Statement  Q is correct.

If function is inverse then function will be onto as well, statement R is also correct.