GATE CS 2016 Set 1 Q28 — Sets, Relations and Functions

To find the maximum possible size of the range $R$, we analyze the given properties of the function $f: \mathbb{N}^+ \rightarrow \mathbb{N}^+$:

1. Even rule: $f(n) = f(n/2)$ when $n$ is even. This implies that the value of $f(n)$ is determined entirely by the odd part of $n$. That is, if $n = 2^a \cdot m$ where $m$ is odd, then $f(n) = f(m)$.
2. Odd rule: $f(n) = f(n+5)$ when $n$ is odd. Since $n+5$ is even, applying the even rule gives: $$f(n) = f\left(\frac{n+5}{2}\right)$$

Let us trace this relation for odd integers $n$:

• For $n = 1$: $f(1) = f\left(\frac{1+5}{2}\right) = f(3)$. Thus, $f(1) = f(3)$.
• For $n = 3$: $f(3) = f(1)$.
• For $n = 5$: $f(5) = f\left(\frac{5+5}{2}\right) = f(5)$.
• For $n = 7$: $f(7) = f(6) = f(3) = f(1)$.
• For $n = 9$: $f(9) = f(7) = f(1)$.
• For $n = 11$: $f(11) = f(8) = f(1)$.

By induction, we can classify all positive integers into two equivalence classes based on whether they are multiples of $5$:

• Not a multiple of 5: All such integers eventually map to $f(1)$.
• Multiple of 5: All such integers eventually map to $f(5)$.

Thus, the range of $f$ can contain at most $2$ distinct values: $R = \{f(1), f(5)\}$. We can construct a valid function $f$ where $f(1) \neq f(5)$ (for example, $f(n) = 2$ if $5 \mid n$, and $f(n) = 1$ otherwise). Therefore, the maximum possible size of $R$ is $2$.