GATE 2016 CS – Question 38
A function $f : \mathbb{N}^+ \rightarrow \mathbb{N}^+$, defined on the set of positive integers $\mathbb{N}^+$, satisfies the following properties:
$f(n) = f(n/2)$ if $n$ is even
$f(n) = f(n+5)$ if $n$ is odd
Let $R = \{i \mid \exists j : f(j) = i\}$ be the set of distinct values that $f$ takes. The maximum possible size of $R$ is ________.
Practise this question in The GATE Grind →
Show answer and explanation
Correct answer: 2
Explanation
The rules force many values to be equal: $f(1) = f(6) = f(3) = f(8) = f(4) = f(2) = f(1)$, so $f(1), f(2), f(3), f(4), f(6), f(8)$ are all the same. Then $f(7) = f(12) = f(6)$ and $f(9) = f(14) = f(7)$ join that group too. The value $f(5)$ is only tied to $f(10) = f(5)$, so it is free, and numbers like $f(15) = f(20) = f(10) = f(5)$ attach to it. Every positive integer ends up in one of these two groups, so $f$ takes at most 2 distinct values.