PUERTA | GATE-CS-2014-(Conjunto-3) | Pregunta 62

Considere el conjunto de todas las funciones f: {0,1, … ,2014} → {0,1, … ,2014} tal que f(f(i)) = i,
para todo 0 ≤ i ≤ 2014. Considere lo siguiente declaraciones:

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. 

¿Cuál de las siguientes es CORRECTA?
(A) P, Q y R son verdaderas
(B) Solo Q y R son verdaderas
(C) Solo P y Q son verdaderas
(D) Solo R es verdadera

Respuesta: (B)
Explicación: Este tipo de funciones se llaman funciones identidad .

Suponemos f(i) = k. Entonces, f(k) = i. Ahora, dado que los valores de ‘i’ y ‘j’ serían iguales para al menos algunos valores si el dominio y el codominio se cruzan, lo cual es cierto para la pregunta dada, Q es definitivamente cierto. Pero esto podría no suceder para todos los valores de ‘i’, por lo tanto, P no siempre es cierto.

Ahora, ‘i’ va de 0 a 2014, por lo que toma 2015 valores posibles. De la definición de una función, sabemos que para cada entrada a la función, tenemos una salida única. Además, en la pregunta dada, el dominio y el codominio son exactamente iguales. Por lo tanto, la función es sobre y, por lo tanto, R es definitivamente verdadera.

Por lo tanto, la opción correcta es B.
Cuestionario de esta pregunta