Function Olympiad Problem: Define $f(n)$ such that $f(n)$ is a positive integer, $f(n+1)$ $>$ $f(n)$ and $f(f(n))$ $=$ $3n$. The value of $f(10)$ is?

If you know me at all, or have read my profile, or have seen any of my previous questions, you might know that I am very interested in Olympiad maths and have come across many challenging maths problems, although I'm not too strong in the functions department myself. Could you please help me with the following problem? Again, any help and contributions are greatly appreciated.

For each positive integer $n$, define $f(n)$ such that $f(n)$ is a positive integer, $f(n+1)$ $>$ $f(n)$ and $f(f(n))$ $=$ $3n$. The value of $f(10)$ is?

This was a multiple choice question, and the possible answers were (A)12, (B)15, (C)19, (D)21, (E)30

Okay, so far I know that this function must be injective because it is strictly increasing, because $f(n+1) > f(n)$. I don't think that we can know yet if this function is surjective or not.

This shouldn't be too much of a hassle for most experienced mathematicians (like the users of this site) but for me it makes little sense. And I try, I really do! Just now I searched what injective and surjective means, and I finally understand that much, so... yea. Improvement.

Anyway, any help or contributions will be greatly appreciated. Thank you! :)

-
You can easily narrow it down to between 18 and 27. – karakfa Mar 21 '13 at 19:51

First note that $f(f(1)) = 3 \implies f(1) = 2$ (Why?) This gives us $f(2) = 3$. $$f(f(2)) = 3 \times 2 = 6 \implies f(3) = 6$$ $$f(f(3)) = 3 \times 3 = 9 \implies f(6) = 9$$ Since we have $$6 = f(3) < f(4) < f(5) < f(6) = 9$$ and all are positive integers, we get $f(4) = 7$ and $f(5) = 8$ (Why?). Now $$f(f(4)) = 3 \times 4 = 12 \implies f(7) = 12$$ $$f(f(5)) = 3 \times 5 = 15 \implies f(8) = 15$$ $$f(f(6)) = 3 \times 6 = 18 \implies f(9) = 18$$ $$f(f(7)) = 3 \times 7 = 21 \implies f(12) = 21$$ Again, since $$18 = f(9) < f(10) < f(11) < f(12) = 21$$ and all are positive integers, we get that $$f(10) = 19$$

EDIT

If I plug in these values in OEIS, it gives this, the unique monotonic sequence of non-negative integers satisfying $a(a(n)) = 3n$.

-
Very nice answer. Thanks! – mathsnoob Mar 21 '13 at 19:57

Given the choices (A)12, (B)15, (C)19, (D)21, (E)30

As you need to evaluate $f(10)$ satisfying the equation $f(f(n)) = 3\cdot n$, so

$f(n) = 10 = f(f(n_i)) = 3\cdot n_i$

But $10 \ne 3\cdot n_i$, so $f(10) \ne 3\cdot n$

Thus the answer is (C) 19

-