in Set Theory & Algebra retagged by
11,569 views
68 votes
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?

  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
in Set Theory & Algebra retagged by
11.6k views

4 Comments

How do you guys get this view of answering the question in the exam?
2
2

it has to be the practice and experience with such questions.

1
1

...

0
0

4 Answers

102 votes
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.
edited by
by

4 Comments

Need one clarification for option A) what if we map 0 to 0, 1 to 1, 2 to 2 ....2014 to 2014. In that case f(f(i))=is satisfying and for every i, f(i) = i also.....
0
0

, yes but p is not necessary.

without p also we can achieve that.

0
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.
0
0
6 votes
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 .

1 comment

You mean one-one and onto...
0
0
2 votes
2 votes

1 comment

edited by
Each function must be onto
0
0
2 votes
2 votes

This is one other way to solve easily,

Ram_Chran

Hence, we can note that Statement P can be eliminated, and Q and R are true.

So, Option (B) will be the answer.

Answer:

Related questions