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

Solution :
\[
f:\mathbb{N}^+ \to \mathbb{N}^+, \quad
f(n)=f\left(\frac{n}{2}\right)\ \text{if } n \text{ even.}
\]
\[
\text{Iska matlab even numbers baar-baar } 2 \text{ se divide hokar kisi odd number par aa jaate hain,}
\]
\[
\text{isliye even numbers koi nayi value nahi dete.}
\]
\[
\text{Odd } n \text{ ke liye } f(n)=f(n+5), \text{ jisse odd numbers groups me link ho jaate hain.}
\]
\[
\text{Odd numbers check karte hain: }
1 \rightarrow 6 \rightarrow 3 \rightarrow 8 \rightarrow 4 \rightarrow 2 \rightarrow 1 \ (\text{ek group}),
\]
\[
5 \rightarrow 10 \rightarrow 5 \ (\text{alag group}).
\]
\[
7 \rightarrow 12 \rightarrow 6 \rightarrow 3,\
9 \rightarrow 14 \rightarrow 7,\
\text{aur baaki } (11,13,\ldots) \text{ sab 1 wale group me merge ho jaate hain.}
\]
\[
\text{Isliye sirf 2 independent groups bachte hain: ek 1 se start hone wala aur ek 5 se start hone wala.}
\]
\[
\therefore \text{ Maximum possible size of } R = \boxed{2}.
\]
 

---

Ans

---

awesome question!!

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

thanks

---

it should be f(2/2) = 1 and not f(2/1) = 1 . Fix the typo please

---

great answering sir but pretty dangerous question

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

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

---

2

Answer 5

Answer 2..

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

Comments

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

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.