# GATE2016-1-28

7.8k views
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 ___________.
5

Interesting recursive functions -

0

@MRINMOY_HALDER To be frank, the question is related to that conjecture.

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.$

selected by
8
serioulsy this was best explnation :)
0
0
why only y values are counted...y not x values ???
0

et R={i∣∃j:f(j)=i} be the set of distinct values that...
can sum1 explain clearly ???wat is d meaning of dis

0
0
Nice Explanation Boss..
0
Kya baat hai, amazing bro!
5

R={i∣∃j:f(j)=i} be the set of distinct values that f takes

Someone please explain why is it written "takes" ?  R contains the values that f can "give" right?

0

@MINIPanda it is recursive function.

f(x){

if (x==1)

return x;   //map to "x"

else if (x==5)

return y; map to "y"   // base condition

if (x mod 2 == 0)

f(x/2)

else

f(x+5)

}

Function assign value to it when it terminates. As you can see base value can be either 1 or 5. R = {1,5}

PS: Recursive fun calls doesn't provide mapping. A value is mapped when function terminates and return something.

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

even this is ambiguous as everything boils down to f(1) and f(5) it should be mentioned that we can consider f(x)=x coz R contains all values such that there exist at least one value in Domain which should map to this x.

0
@sunita24 Actually, answers written from book are copied from here!
0
We just checked first few cases.. how to prove there are only 2 equivalence classes?
1

@Divy Kala I have written the code above for the same. Please check it and let me know if you still have doubt.

Its Saying we have 2 domains
N+ → N+

1. So F(1) = F(6) = F(3) = F(8) = F(4) = F(2) = F(1)....It Repeats...  Now F(7) = F(12) = F(6)...Again repeats both above are same...Since F(6) matches in both so same both belongs to same value.We are not getting F(5) above
2. Now F(5) = F(10) = F(5)..Repeats ...We can see we have different value for multiples of 5 and other natural numbers.

edited
5

can anyone explain meaning of this plz??

6
can you please explain what is the meaning of this statement

$R = \{i | \exists j : f(j) = i \}$

f(5) and f(10) is multiple of 5, that is true. But how they are equal, as we can see f(5) = 10 and f(10) = 5.

Also the problem doesn't want to know about the multiple of x, isn't it??

Problem is very much unclear to me..? If you explain a bit more it will be helpful.
11
its f(n)=f(n/2) , and not f(n)=n/2, and similarly for the other one, read carefully
0
doubt 1> if i = 1,2,3,4,6,7,8,12 have calling each other then why size of R is not 9 as i can have values 1,2,3,4,6,7,8,12  and 5 too.

doubt 2> what is about 9. 9 is not comming in 1,2,3,4,6,7,8,12.

0
Thank you for so nice explanation.
0

Deepesh Kataria .where is f(9)

0
f(9) = f(9+5)= f(14)= f(14/2)= f(7)

now f(7) = f(7+5)= f(12)=f(12/2)= f(6)=f(3)=f(8) etc.

for multiples of 5.. f(5)=f(10)...
and one for rest of the numbers in N.
0
can you please explain what is the meaning of this statement

$R = \{i | \exists j : f(j) = i \}$

f(5) and f(10) is multiple of 5, that is true. But how they are equal, as we can see f(5) = 10 and f(10) = 5.

Also the problem doesn't want to know about the multiple of x, isn't it??

Problem is very much unclear to me, that is why I am unable to understand the answer ? If you explain a bit more it will be helpful.
15
i.e., set notation. Here we are defining a set R and we include all i in R such that there exists j such that f(j) = i. Here, j is from natural number set. f(5) = f(10) = f(15) = f(20) = ... = say x. Also, f(2) = f(3) = f(4) = f(6) = ... say y. So, to maximize the number of elements in R, we can take $x \neq y$ making 2 possible elements in R.
0

Thanks
0
@arjun sir,f(5) = 10

then why r u again finding f(10) and then again finding function of f(10)

what you are doing is f(f(f(......f(5)))) =5

whya re you doing this??

the set definition does not ask for this..

pls explain
0

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

here the set definition means that

take suppose j=1 then f(1) =6 ,this 6 is i

f(2) = 1 ,this 1 is i

f(3) =8 ,this 8 is i

f(4) = 2 ,this 4 is i

.

.

.

this way we get so many values of i which form N+ set only {1 , 2 , 3 ,4 .....}

then why are you doing f(1) =f(6) =f(3) =f(8)...??

the set builder form is not asking this.

6

@akriti, see defination of function again, it's in recursive form f(n) = f(n/2) ( see the recursion)  f(1) = f(6) so in order to cal. f(1) we need to agin cal f(6) now this will give f(3) now again we need to fine f(3) which will be f(8).now f(8)will give f(4) and then f(4) will give f(2) and then f(2) -> f(1) so in this way it repeats itself. see the function again, the catchy thing is the recursion part.

2
ooh..i missed the recursion part..thanks @mohit..:-)

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
1
How to think like this in exam??
1
Take i= 1,2,3,,...10 and solve it. then you will see a pattern in it then generalize it.
0

Best solution by using mathematical Induction.Thanks :-)

0
Hi Sachin,

How "If n is odd, f(n)=f(n−5)" this is true?
0

@Sourav Basu
Yes.

$\because f(n)=f(n+5)$.

Putting $n=n-5$ [where $n>5$] will yield $f(n-5)=f(n-5+5)=f(n)$

$\text{let we have f(1) = x. Then, f(2) = f(2/2) = f(1) = x}$

$\text{f(3) = f(3+5) = f(8) = f(8/2) = f(4/2) = f(2/1) = f(1) = x }$
$\text{f(5) = f(5+5) = f(10/2) = f(5) = y. }$

$\text{All$N^+$except multiples of 5 are mapped to x and multiples}$

$\text{of 5 are mapped to y so ,$\mathbf{Answer\space is\space 2}$}$

edited
1

thanx @Prince Sindhiya  ,the pictorial mapping clears everything.,

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.

1 vote

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.

## Related questions

1
9.7k views
Consider the weighted undirected graph with $4$ vertices, where the weight of edge $\{i,j\}$ is given by the entry $W_{ij}$ in the matrix $W$. W=$\begin{bmatrix} 0&2 &8 &5 \\ 2&0 &5 &8 \\ 8&5 &0 &x \\ 5& 8 &x &0 \end{bmatrix}$ The largest possible integer value of $x$, for which at least one shortest path between some pair of vertices will contain the edge with weight $x$ is ___________.
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 spanning tree of $G$ can have is __________
For a host machine that uses the token bucket algorithm for congestion control, the token bucket has a capacity of $1$ $\text{megabyte}$ and the maximum output rate is $20$ $\text{megabytes}$ per $\text{second}$. Tokens arrive at a rate to sustain output at a ... machine needs to send $12$ $\text{megabytes}$ of data. The minimum time required to transmit the data is _____________ $\text{seconds}$.
Cylinder a disk queue with requests for $I/O$ to blocks on cylinders $47, 38, 121, 191, 87, 11, 92, 10.$ The C-LOOK scheduling algorithm is used. The head is initially at cylinder number $63$, moving towards larger cylinder numbers on its ... The cylinders are numbered from $0$ to $199$. The total head movement (in number of cylinders) incurred while servicing these requests is__________.