Waste less time on Facebook — follow Brilliant.
×

Functional Relation

I don't even know how to proceed on this problem.

Let f:N \(\rightarrow\) N be a function such that f(n+1)>f(n) and f(f(n))=3n \(\forall\) n. Evaluate f(2010).

Please help.....

Note by Nishant Sharma
4 years, 3 months ago

No vote yet
3 votes

Comments

Sort by:

Top Newest

Use base systems :)

For any integer \( n \) , let \( n_{[3]} \) denote the base \( 3 \) representation of \( n \) . Let \( n_{[3]} = a_1a_2a_3 \cdots a_k \) Then by using induction we can prove that \[ f(n)_{[3]} = 2a_2a_3 \cdots a_k , \ \text{if} \ a_1 = 1 \] and , \[ f(n)_{[3]} = 1a_2a_3 \cdots a_k0 ,\ \text{if} \ a_1 = 2 \] .

Now using this ,since \( 2010_{[3]} = 2202010 \) we get \( f(n)_{[3]} = 12020100 \) Which gives \( f(n) = \boxed{3816} \) \( \blacksquare \) Shivang Jindal · 4 years, 3 months ago

Log in to reply

@Shivang Jindal I was quite familar with this technique actually . I had solved a simlar type of problem earlier too and quite familiar with this technique . Base systems are very hand in solving many NT and FE problems . Shivang Jindal · 4 years, 3 months ago

Log in to reply

@Shivang Jindal No doubt you are familiar with the technique but what I want to know is on what grounds can one use base systems to solve FE ? I mean what are the requirements and also please explain the procedure a bit. Nishant Sharma · 4 years, 3 months ago

Log in to reply

@Nishant Sharma See this nice article from IMO compendium group : click here See P20 . You would get the point Shivang Jindal · 4 years, 3 months ago

Log in to reply

@Shivang Jindal It was good but since I am not much familiar with these type of techniques I was not able to grasp it completely. Though indirectly you gave a nice link to the general methods of solving FE. Great !!! Nishant Sharma · 4 years, 3 months ago

Log in to reply

@Shivang Jindal I couldn't get how did u get the idea of using a different base representation and again with a specific 3... when one have to consider this concept of base system ......?..please elaborate....regards.... Raja Metronetizen · 4 years, 3 months ago

Log in to reply

@Shivang Jindal hats off to thinking procedure & art of problem solving... Raja Metronetizen · 4 years, 3 months ago

Log in to reply

@Shivang Jindal Even though your soln seems to be concise and simple, but I couldn't get how did you get the idea of using a different base representation and that too only 3 ? Please guide me a bit further. I'd be grateful to you for that. Nishant Sharma · 4 years, 3 months ago

Log in to reply

@Shivang Jindal Fantastic! Gabriel Wong · 4 years, 3 months ago

Log in to reply

Here's a suggestion on how to start with the problem:

We know that \(f(f(1))=3\). What are the possible values of \(f(1)\)?

Hint: If \(f(1)=1\) then \(f(f(1))=1\). If \(f(1)=4\) then \(f(4)=3\), but \(f(4)>f(3)>f(2)>f(1)\).

Now think about \(f(n)\) for larger values of \(n\). For example, what is \(f(3)\)? Ang Yan Sheng · 4 years, 3 months ago

Log in to reply

@Ang Yan Sheng Ohhhh....I didn't even think that way. So that way and using mathematical induction, f(n)=n+1. Am I right ? Nishant Sharma · 4 years, 3 months ago

Log in to reply

@Nishant Sharma no. its simple to obtain:

f(1) =2

f(2) = 3

f(3) = 6

f(4) = 7 (implied by f(6))

f(5) = 8 (implied by f(6))

f(6) = 9 (follows from f(3))

f(7) = 12 (follows from f(4))

f(8) = 15 (follows from f(5))

f(9) = 18 (follows from f(6)) Gabriel Wong · 4 years, 3 months ago

Log in to reply

@Gabriel Wong ya got your point. I'm working on it.... Nishant Sharma · 4 years, 3 months ago

Log in to reply

@Gabriel Wong ya I was wrong......By the way how did u obtain values f(4) onwards ? Nishant Sharma · 4 years, 3 months ago

Log in to reply

@Nishant Sharma I edited the previous post to show the flow of logic... it does look like induction will work, but you need to notice the pattern. Gabriel Wong · 4 years, 3 months ago

Log in to reply

Comment deleted May 04, 2013

Log in to reply

@Francisco Rivera We are given that \( f : \mathbb{N} \to \mathbb{N} \); that is, \( f \) is a function that maps positive integers to POSITIVE INTEGERS. Your function does not satisfy this criterion. Hero P. · 4 years, 3 months ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...