GATE CS 2016 Set 1 — Question 38

The function $f$ is determined by the recurrence relations. Since $f(n) = f(n/2)$ for even $n$, the value of $f(n)$ depends only on the odd part of $n$. We can restrict our attention to odd integers.For an odd integer $n$, the relation is $f(n) = f(n+5)$. Since $n$ is odd, $n+5$ is even. Let $n+5 = 2^k \cdot m$, where $m$ is odd. Then $f(n+5) = f(m)$. Thus, the recurrence defines a directed graph on odd integers where an edge exists from $n$ to the odd part of $n+5$.Let's trace the paths for various odd integers:

• $1 \to 1+5=6 \to 3$
• $3 \to 3+5=8 \to 1$

This forms a cycle: $1 \leftrightarrow 3$. All numbers reaching this cycle must take the same value $f(1) = f(3)$.

• $5 \to 5+5=10 \to 5$

This forms a self-loop (cycle of length 1): $5 \to 5$. All numbers reaching this cycle must take the value $f(5)$.Let's check if there are other cycles. The condition for a cycle of length 1 is $n = \text{odd}(n+5)$, which implies $n(2^k-1) = 5$. Since $n$ is odd, the only solution is $n=5$ (with $k=1$).
The condition for a cycle of length 2 ($n_1 \to n_2 \to n_1$) leads to $n_1(2^{a+b}-1) = 5(1+2^a)$. For non-multiples of 5, this yields the solution $n=1, 3$.It can be shown that all multiples of 5 eventually reach the fixed point 5, and all non-multiples of 5 eventually reach the cycle $\{1, 3\}$.Since there are exactly two disjoint components (basins of attraction) in this functional graph, we can assign a distinct value to each component. For example, let $f(n) = A$ for all $n$ in the first component and $f(n) = B$ for all $n$ in the second component. If $A \neq B$, the range $R$ has size 2.Thus, the maximum possible size of $R$ is 2.