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

#HelpMe! #MathProblem

This discussion board is a place to discuss our Daily Challenges and the math and science related to those challenges. Explanations are more than just a solution — they should explain the steps and thinking strategies that you used to obtain the solution. Comments should further the discussion of math and science.

When posting on Brilliant:

Use the emojis to react to an explanation, whether you're congratulating a job well done , or just really confused .
Ask specific questions about the challenge or the steps in somebody's explanation. Well-posed questions can add a lot to the discussion, but posting "I don't understand!" doesn't help anyone.
Try to contribute something new to the discussion, whether it is an extension, generalization or other idea related to the challenge.
Stay on topic — we're all here to learn more about math and science, not to hear about your favorite get-rich-quick scheme or current world events.

Markdown	Appears as
`italics` or `_italics_`	italics
`bold` or `__bold__`	bold
- bulleted - list	bulleted list
1. numbered 2. list	numbered list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1 paragraph 2	paragraph 1 paragraph 2
`[example link](https://brilliant.org)`	example link
`> This is a quote`	This is a quote
# I indented these lines # 4 spaces, and now they show # up as a code block. print "hello world"	# I indented these lines # 4 spaces, and now they show # up as a code block. print "hello world"

Math	Appears as
Remember to wrap math in `$` ... `$` or `\[` ... `\]` to ensure proper formatting.
`2 \times 3`	$2 \times 3$
`2^{34}`	$2^{34}$
`a_{i-1}`	$a_{i-1}$
`\frac{2}{3}`	$\frac{2}{3}$
`\sqrt{2}`	$\sqrt{2}$
`\sum_{i=1}^3`	$\sum_{i=1}^3$
`\sin \theta`	$\sin \theta$
`\boxed{123}`	$\boxed{123}$

Comments

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 - 8 years, 1 month ago

Ohhhh....I didn't even think that way. So that way and using mathematical induction, f(n)=n+1. Am I right ?

Nishant Sharma - 8 years, 1 month ago

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 - 8 years, 1 month ago

@Gabriel Wong – ya got your point. I'm working on it....

Nishant Sharma - 8 years, 1 month ago

@Gabriel Wong – ya I was wrong......By the way how did u obtain values f(4) onwards ?

Nishant Sharma - 8 years, 1 month ago

@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 - 8 years, 1 month ago

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 - 8 years, 1 month ago

Fantastic!

Gabriel Wong - 8 years, 1 month ago

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 - 8 years, 1 month ago

hats off to thinking procedure & art of problem solving...

Sayan Chaudhuri - 8 years, 1 month ago

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

Sayan Chaudhuri - 8 years, 1 month ago

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 - 8 years, 1 month ago

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 - 8 years, 1 month ago

@Nishant Sharma – See this nice article from IMO compendium group : click here See P20 . You would get the point

Shivang Jindal - 8 years, 1 month ago

@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 - 8 years, 1 month ago

Math	Appears as
Remember to wrap math in `\(` ... `\)` or `\[` ... `\]` to ensure proper formatting.
`2 \times 3`	$2 \times 3$
`2^{34}`	$2^{34}$
`a_{i-1}`	$a_{i-1}$
`\frac{2}{3}`	$\frac{2}{3}$
`\sqrt{2}`	$\sqrt{2}$
`\sum_{i=1}^3`	$\sum_{i=1}^3$
`\sin \theta`	$\sin \theta$
`\boxed{123}`	$\boxed{123}$