Dark Mode

11,569 views

68 votes

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?

- $P, Q$ and $R$ are true
- Only $Q$ and $R$ are true
- Only $P$ and $Q$ are true
- Only $R$ is true

102 votes

Best answer

Let $f(i) = j$. Now, we have $f(j) = i$, as per the given condition $f(f(i)) = i$.

For any $i \neq j$, we can have a mapping $f(i) = j, f(j) = i$ thus avoiding the condition $f(i) = i$. But since the domain set contains odd number of elements, at least for one element we must have $f(i) = i$. So, Q must be TRUE.

Since $f(i) = j$ and $f(j) = i$, and since $0 \leq i \leq 2014$ $i$ must take all 2015 possible values (since $f$ is a function, it must have a value for any element in the domain). We can easily see that $f(i)$ cannot be the same for two different $i$s- because suppose $f(2) = 5$, and $f(3) = 5$. Now as per given condition, $f(5) = 2$ and $f(5) = 3$, which is not allowed in a function. So, all $f(i)$ values are unique $\implies$ co-domain $=$ range as there are only $2015$ values in co-domain. So, R is true.

An identity function satisfies the given conditions. But that alone cant prove that P is true. We can also have a different function where all even numbers maps to the next odd number and all odd numbers map to the previous even number which satisfies the given conditions, except the last one as we have odd number in set. i.e.,

$f(0) = 1, f(1) = 0, f(2) = 3, f(3) = 2 \dots, f(2013) = 2012, f(2014) = 2014$.

This proves, P is false.

So, (B) is the answer.

For any $i \neq j$, we can have a mapping $f(i) = j, f(j) = i$ thus avoiding the condition $f(i) = i$. But since the domain set contains odd number of elements, at least for one element we must have $f(i) = i$. So, Q must be TRUE.

Since $f(i) = j$ and $f(j) = i$, and since $0 \leq i \leq 2014$ $i$ must take all 2015 possible values (since $f$ is a function, it must have a value for any element in the domain). We can easily see that $f(i)$ cannot be the same for two different $i$s- because suppose $f(2) = 5$, and $f(3) = 5$. Now as per given condition, $f(5) = 2$ and $f(5) = 3$, which is not allowed in a function. So, all $f(i)$ values are unique $\implies$ co-domain $=$ range as there are only $2015$ values in co-domain. So, R is true.

An identity function satisfies the given conditions. But that alone cant prove that P is true. We can also have a different function where all even numbers maps to the next odd number and all odd numbers map to the previous even number which satisfies the given conditions, except the last one as we have odd number in set. i.e.,

$f(0) = 1, f(1) = 0, f(2) = 3, f(3) = 2 \dots, f(2013) = 2012, f(2014) = 2014$.

This proves, P is false.

So, (B) is the answer.

0

I understood the explanation given above but I have one doubt.

Generally speaking, if f(x)=f inverse(x) then they intersect at y=x line as they are symmetric about this line.

f(i) = f inverse(i) = i.

Question says ff(i) = i for all i between 0 to 2014 then f(i) should be equal to i for all i b/w 0 to 2014.

Then why P is wrong it does not matter whether the domain is odd or even.

Generally speaking, if f(x)=f inverse(x) then they intersect at y=x line as they are symmetric about this line.

f(i) = f inverse(i) = i.

Question says ff(i) = i for all i between 0 to 2014 then f(i) should be equal to i for all i b/w 0 to 2014.

Then why P is wrong it does not matter whether the domain is odd or even.

0

6 votes

i think ans is B)

yes this function is into and onto .

as the P says for each i there must be a f(i)= i its may true but not the essential condition . as there must be like this f(0)=2014 and f(2014)= 0 so , f(f(0))=0

for Q its true , there must be atleast one element have to satisfy this condition f(i)= i .

and R is also true .

2 votes