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

😂

---

@MRINMOY_HALDER i immediately thought of this video when i first started to break down the function ! :D

 

Answer 1

 F(1) = F(6) = F(3) = F(8) = F(4) = F(2) = F(1).

arrange in ascending order

1,2,3,4,6,8   

Take n=5

5,10,5,10,5,10

Take n=5

7,12,6,3   F(6) matches in both so same both belongs to same value.

Take n=9

9,14,7     F(7) matches in both so same both belongs to same value.

We can see we have different value for multiples of 5 and other natural numbers.