GATE2016-1-28

Question

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

Comments

Interesting recursive functions - 

Answer 1

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

Comments

serioulsy this was best explnation :)

---

best answer...

---

why only y values are counted...y not x values ???

---

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

---

bookish explanations eveywhere on this page...

---

Nice Explanation Boss..

---

Kya baat hai, amazing bro!

---

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?

---

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

---

@sunita24 Actually, answers written from book are copied from here!

---

We just checked first few cases.. how to prove there are only 2 equivalence classes?

---

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

Answer 2

Answer is 2
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.

Comments

can anyone explain meaning of this plz??

---

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.

---

its f(n)=f(n/2) , and not f(n)=n/2, and similarly for the other one, read carefully

---

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.

please clear these doubts

---

Thank you for so nice explanation.

---

@ Deepesh Kataria .where is f(9)

---

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.

Answer 3

Answer 2..

for multiples of 5.. f(5)=f(10)...
and one for rest of the numbers in N.

Comments

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.

---

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.

---

please explain in detail

 

Thanks

---

@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

---

 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.

---

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

---

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

Answer 4

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

Comments

How to think like this in exam??

---

Take i= 1,2,3,,...10 and solve it. then you will see a pattern in it then generalize it.

---

Best solution by using mathematical Induction.Thanks :-)

---

Hi Sachin,

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

---

@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)$

Answer 5

$\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}$}$

 

 

Comments

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

Answer 6

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.