1
$\begingroup$

A function $f: \Bbb{N^+} \rightarrow \Bbb{N^+}$ , defined on the set of positive integers $\Bbb{N^+}$,satisfies the following properties: $$f(n)=\begin{cases} f(n/2) & \text{if } n \text{ is even}\\ f(n+5) & \text{if } n \text{ is odd} \end{cases}$$ 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 ___________.

Answer of this question is $2$, and solution goes like this:-
every multiple of $5$ has same value, and every other number has same value.

I want to proof it, by NOT using examples, but some real mathematical proof, that can show us that indeed this is true.

Thanks.

$\endgroup$
1
$\begingroup$

Suppose that $f(1) = a$ and $f(5) = b$. It is clear that $$f(5n) = b$$ for all $n$. We'll prove by induction that for all $n \ne 5k$, $f(n) = a$. First note that $$f(2) = f(\frac{2}{2}) = f(1) = a,$$ $$f(3) = f(3+5) = f(8) = f(4) = f(2) = a,$$ $$f(4) = f(2) = a.$$ Now suppose $n = 5k + r$, where $0 < r < 5$, and for all $m<n$ which are not divisible by $5$, $f(m) = a$.

If $n$ is odd, $f(n) = f(n-5)$, and by induction hypothesis, $f(n-5) = a$, so we get $$f(n) = a.$$

If $n$ is even, $f(n) = f(n/2)$, and by induction hypothesis, $f(n/2) = a$, so we get $$f(n) = a.$$

Note that here $\frac{n}{2}$ isn't divisible by $5$.

$\endgroup$
  • $\begingroup$ Excellent work :) Any other method without induction ? And can u plz make it more illustrative as i am not getting it much :( $\endgroup$ – user3699192 Jan 29 '17 at 3:33
  • $\begingroup$ On which part is it that you need more detail? $\endgroup$ – SSepehr Jan 29 '17 at 3:35
  • $\begingroup$ Last part plz, induction hypothesis part. Plz make it in such a way that 10th class student can also get it :) i know that, if we have solution for n=k then we also have solution for n=k+1 (using hypothesis) Your base cases are $f(1)$, $f(2)$, $f(3)$, $f(4)$, right ? and then u said that we have solution for $f(n-5)$ and by hyposthesis we are finiding $f(n)$ ? $\endgroup$ – user3699192 Jan 29 '17 at 3:39
  • $\begingroup$ Yes, $f(1)$, $f(2)$, $f(3)$, $f(4)$ are the base cases, and I'm assuming the hypothesis for all $k<n$, not just $n-1$, so it covers $n-5$ and $n/2$. This is called "strong induction", which is basically equivalent to the usual induction you mentioned. $\endgroup$ – SSepehr Jan 29 '17 at 3:45
  • $\begingroup$ Because if it were, $f(k)$ would be $b$, not $a$. $\endgroup$ – SSepehr Jan 29 '17 at 3:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.