in Set Theory & Algebra edited by
16,767 views
84 votes
84 votes
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 ___________.
in Set Theory & Algebra edited by
16.8k views

4 Comments

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

2
2
Such Questions make the preparation journey more interesting :D
1
1

😂

3
3

8 Answers

182 votes
182 votes
Best answer
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

4 Comments

very nice explanation.
0
0
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
0
0
Got it!🙂🙂
0
0
42 votes
42 votes

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.
edited by

4 Comments

Thank you for so nice explanation.
0
0

Deepesh Kataria .where is f(9)

0
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.
0
0
16 votes
16 votes
Answer 2..

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

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

7
7
ooh..i missed the recursion part..thanks @mohit..:-)
2
2
Thanks for this.…

I was also stuck here

Such silly things 🤦
0
0
13 votes
13 votes

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 by

4 Comments

Best solution by using mathematical Induction.Thanks :-)

0
0
Hi Sachin,

How "If n is odd, f(n)=f(n−5)" this is true?
0
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)$

1
1
Answer:

Related questions