The GATE Grind

GATE 2014 CS (CS3) – Question 59

Engineering Mathematics · Discrete Mathematics: Sets, Relations, Functions, Partial Orders and Lattices · 2 marks · Multiple choice

Consider all $f:\{0,1,\ldots,2014\}\to\{0,1,\ldots,2014\}$ satisfying $f(f(i))=i$. P: Every such function fixes every i. Q: Every such function fixes some i. R: Every such function is onto. Which is correct?

  1. P, Q and R true
  2. Only Q and R true
  3. Only P and Q true
  4. Only R true

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (B) Only Q and R true

Explanation

Sincef(f(i))=i, fis its own inverse and is onto. Its cycles have length1or2; an odd-sized set cannot be partitioned entirely into2cycles, so at least one fixed point exists. Swapping two elements shows not every element need be fixed. Thus **QandRonly,B**.