edited by
21,341 views
91 votes
91 votes
A function $f: \Bbb{N^+} \rightarrow \Bbb{N^+}$ , defined on the set of positive integers $\Bbb{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 ___________.
edited by

9 Answers

13 votes
13 votes

http://math.stackexchange.com/questions/2118739/finding-recursive-function-range/2118749

We will use strong Induction Hypothesis to proof this.

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 \lt r \lt 5$, and for all $k\lt n$, $n$ is not divisible by $5$ bcoz $r \neq 0$
Note that if  $n$ is not divisible by $5$ then $n-5$ is also not divisible by $5$. Because $n-5 = 5(k-1) + r$, again $r \neq 0$.
And also Note that $\frac{n}{2}$ is not divisible by $5$, bcoz if it were divisible by $5$, this will make $n$ divisible by $5$. 

Base case:  $f(1)=f(2)=f(3)=f(4)=a$ [already solved for base cases above]
Incuctive step: Now suppose $n = 5k + r$, where $0 \lt r \lt 5$, and for all $m\lt n$ which are not divisible by $5$, $f(m) = a$.
($m$ already covers $n-5$ and $\frac{n}{2}$)
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.$$

edited by
4 votes
4 votes

choose any number let n=17, then

f(17)=f(22)=f(11)=f(16)=f(8)=f(4)=f(2)=f(1)=f(6)=f(3)=f(8)=f(4)=f(2)=f(1)=f(6)=f(3)=f(8)=f(4)=f(2)=f(1)... <this is one part>

now let n=50

f(50)=f(25)=f(30)=f(15)=f(20)=f(10)=f(5)=f(10)=f(15)=f(20)=f(10)=f(5)=f(10)=f(5)=f(10)=f(5) .....<this is other part>

so we can take any number and that will fall either of any cycle, these are the two types of values that Function f( ) can take.

3 votes
3 votes

Let's start with the smallest number. (You can begin at any number)

$f(1) = f(6) = f(3) = f(8) = f(4) = f(2) = \color{red}{f(1)}... $

$f(2)=\color{red}{f(1)}$

$f(3)=\color{red}{f(1)}$

$f(4)=\color{red}{f(1)}$

$f(5) = f(10) = \color{blue}{f(5)}... $

$f(6)=\color{red}{f(1)}$

$f(7) = f(12) = f(6) =\color{red}{f(1)}$

$f(8)=\color{red}{f(1)}$

$f(9) = f(14) = f(7)=\color{red}{f(1)}$

$f(10)=\color{blue}{f(5)}$

$f(11) = f(16) = f(8)=\color{red}{f(1)}$

... so on.

 

We observe that all the multiples of 5 will have the value of $f(5)$ and every other number will converge to $f(1)$ ultimately.

Let's assume $f(1) = i_1$ and $f(5) = i_2$

$R=\{i∣∃j:f(j)=i\} $

Hence, there are 2 such $i$'s.

0 votes
0 votes

The question can be done by permutation and combination.

A given number “J” belonging to N+  can be odd or even ie 2 distinct values, hence ending function there only. --------------(1)

if function continues then either  odd number can have even or odd value or the even number can have odd or even value . Resulting in 4 distinct values  ------------------(2)

if function continues then either  odd number can have even or odd value or the even number can have odd or even value and so on….. . Resulting in 8 distinct values……….(3)

 

from (1), (2), (3)  a GP is created from the function that can have   2 +  4+ 8+ 16+ 32+…….

the sum taken as absolute value i.e.  2   which is the required value.

 

Answer:

Related questions

85 votes
85 votes
18 answers
2
Sandeep Singh asked Feb 12, 2016
35,081 views
Let $G$ be a complete undirected graph on $4$ vertices, having $6$ edges with weights being $1, 2, 3, 4, 5,$ and $6$. The maximum possible weight that a minimum weight s...