GATE CSE 2016 Set 1 | Question: 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

....….………..................…......…....………….…….…………..

---

Such Questions make the preparation journey more interesting :D

---

Haywire

😂

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

very nice explanation.

---

Whoever is calling it explanation they are wrong. There should be a proof that this should be true always. How you know that it will not faile for say 47 or 4775 in thoery you should have known it before hand otherwise I don’t think you can solve this one

---

Got it!🙂🙂

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

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

---

R is the value of “i” for which f(j) = i.

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..:-)

---

Thanks for this.…

I was also stuck here

Such silly things 🤦

Answer 4

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