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, 6 months ago

No vote yet
3 votes

  Easy Math Editor

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold

- bulleted
- list

  • bulleted
  • list

1. numbered
2. list

  1. numbered
  2. 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"
MathAppears 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

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, 6 months ago

Log in to reply

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, 6 months ago

Log in to reply

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, 6 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, 6 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, 6 months ago

Log in to reply

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, 6 months ago

Log in to reply

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

Raja Metronetizen - 4 years, 6 months ago

Log in to reply

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, 6 months ago

Log in to reply

Fantastic!

Gabriel Wong - 4 years, 6 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, 6 months ago

Log in to reply

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, 6 months ago

Log in to reply

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, 6 months ago

Log in to reply

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

Nishant Sharma - 4 years, 6 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, 6 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, 6 months ago

Log in to reply

Comment deleted May 04, 2013

Log in to reply

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, 6 months ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...