A function $f : N^+ → N^+$, defined on the set of positive integers $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|∃ j : f(j) = i\}$ be the set of distinct values that $f$ takes. The maximum possible size of $R$ is_____?
My attempt:
Let us assume$: f(1) = x.$ Then,
$f(2) = f(2/2) = f(1) = x$
$f(3) = f(3+5) = f(8) = f(8/2) = f(4/2) = f(2/1) = f(1) = x$
Similarly, $f(4) = x$
$f(5) = f(5+5) = f(10/2) = f(5) = y$
So, it will have two values. All multiples of $5$ will have value $y$ and others will have value $x$. It will have $2$ different values.
Can you explain in formal way, please?
Suppose you calculated $f$ from $1$ to $5$ as you did. Now suppose you know the value of $f(i)$ with $1 \leq i \leq n$ and you have got only $2$ values. Can you calculate $f(n+1)$? Of course: if it is even it is equal to $f((n+1)/2)$ which is $x$ or $y$, if it is odd it is $f((n+1)-5)$ which is $x$ or $y$ (note that $n+1-5=n-4>0$ so it is a good value for $f$).
What is left to be shown now is that such a function exists: keep the function which is $1$ when $n$ is not divisible by $5$ and $2$ when $n$ is divisible by $5$ and check that it satisfies the two requests. Namely notice that dividing by $2$ or subtracting $5$ doesn't change the fact of being or not being divisible by $5$, so you can reduce every $n$ to a number between $1$ and 5 without changing his divisibility by $5$.