Exams › GATE › Technical

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 such function must be onto. Which one of the following is CORRECT?

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

Correct answer: Only Q and R are true

Solution

Statement Q is true because if f(f(i)) = i, then there must be at least one value i for which f(i) equals i, indicating a fixed point. Statement R is also true since the function must map every element in the domain to an element in the codomain, ensuring that it is onto. However, statement P is false because it is possible for f(i) to be different from i while still satisfying f(f(i)) = i.

Related GATE Technical questions

• Let G = (V,E) be a directed graph where V is the set of vertices and E the set of edges. Then which one of the following graphs has the same strongly connected components as G ?
• Consider the following program in C language: #include <stdio.h> main() { int i; int *pi = &i; scanf("%d", pi); printf("%d ", i+5); } Which one of the following statements is TRUE?
• Let G be a graph with n vertices and m edges. What is the tightest upper bound on the running time of Depth First Search on G, when G is represented as an adjacency matrix?
• Let P be a quicksort program to sort numbers in ascending order using the first element as the pivot. Let t1 and t2 be the number of comparisons made by P for the inputs [1 2 3 4 5] and [4 1 5 3 2] respectively. Which one of the following holds?
• Which one of the following is TRUE ?
• Match the following: 1) Waterfall model 2) Evolutionary model 3) Component-based software engineering 4) Spiral development a) Specifications can be developed incrementally b) Requirements compromises are inevitable c) Explicit recognition of risk d) Inflexible partitioning of the project into stages

⚔️ Practice GATE Technical free + battle 1v1 →